▲ 92 points
back
24 comments
I almost always prefer text over video, but this video on the same subject is fantastic: https://www.youtube.com/watch?v=h7apO7q16V0. I watch it at least once every year.
Also, the title of the blog post (and by extension this HN post) is IMO not really correct: it's not about the DFT but specifically about the FFT.
Not going to lie, I have always been fascinated by the fourier transform, but I had to stop this video after less than 2 minutes in because it went way over my head... "a context you are all familiar with: polynomial multiplication"... um no, I have zero clue what that is, sorry. Also the speaker seems to have some sort of speech pathology that unfortunately bothers me.
Polynomial multiplication is something I learned in 8th grade?
I like this 3Blue1Brown video about what he calls the almost-fuerier transform:
www.youtube.com/watch?v=spUNpyF58BY
I first learned about FFT in highschool to solve competitive programming problems, and it was, let's say, useful for that. But then I started studying EE, and after learning more about the different types of Fourier transform, I started respecting the humble DFT matrix much more. I believe there is big gap of understanding between considering FFT as a cool algorithm for multiplying polynomials (or doing a circular convolution), and considering the transform as obtaining an eigenvalue representation of linear systems. The latter might not be as fruitful in the software engineering per se, but is the backbone of understanding the Fourier Transform for EE.
Feels like an article wrote from somebody who knows a lot about the FFT for people who already knows a lot about the FFT.
All mathematic exposition feels that way.
If you are doing polynomial multiplication and want exact integer convolution then you can’t leave the precision of your FFT up to chance so the alternative to an FFT over complex roots of unity is to use something called a Number Theoretic Transform (NTT) that relies on nth roots of unity in finite integer rings
From what I've read about it all in the past, I feel like my intelligence level sits precisely between DCT and DFT. I seem to be able to mostly get Discrete Cosine Transform, but when confronted with Discrete Fourier Transform my brain simply shuts off and melts.
If you wanted to multiply two polynomials f and g of degree n, you could do distribution and the do n squared multiplications. Instead, evaluate the two separate polynomials at 2n special points, multiply the results pointwise, and then interpolate. The magical part is there are some specific points which speed up the evaluation and interpolation steps using a divide and conquer type algorithm.
TeX tip: it's \log, not log (ditto sin, cos, etc)
While I do understand that O(n²) complexitity is frowned upon, I wonder how big should n be before n² multiplications are worse than nlogn loops which include several complex multiplications, complex exp, and various array reshapes...
How much is fft used for AI? Seems that attention and convolution could benefit from this.
There are architectures, such as FNO, that utilize FFTs within them. These are particularly popular in deep learning weather prediction problems.
Somewhat off topic rant, but am I the only one who find mathematical notation unnecessarily obtuse?
The bit that gets me is defining degree as n-1. For someone without a mathematical background, it takes a bit of pondering to figure out that you have to define n as one more than the actual degree, the opposite of what seems natrual. My mind at least just wants to think about n as the degree, and use n+1 as the last index. To me it seems aggressively unintuitive.
I guess you want to align the coefficient numbers but would it be a sin to define another index c = n-1 for that purpose?
But I'm a mathematical lightweight and maybe mathematical thinking is all about this. Perhaps some greater talent can correct my thinking.
Fence post and rail is "off by one", two fence posts are joined by one rail, N fence posts are joined by N-1 rails, and this polynomial order and defining coefficients discussion has that in common.
Two points define a line, a polynomial of degree 1. A polynomial with 2 coefficients, ax + b.
Three points give us a quadratic, a polynomial of degree 2 with three coefficients, ax^2 + bx + c.
N points gives us a polynomial of degree N-1 with N coefficients.
Indexing coefficients by their associated power of X seems natural to some.
A(N-1).X^(N-1) + ... A(1).X^1 + A(0).X^0 (where X^0 == 1)
are the N indexed coefficients of a generic polynomial of order N-1.
By giving it a quick read I saw that the have n data points where a polynomial of n-1 degrees provides a useful fit in the sense of this blog post.
Every field has its own language to speak. And shouting into the field from "outside" that they should change is not polite.
E.g * if you redefine c = n-1 the connection between number of points and dimension is lost. * c ist very often used as a constant Skalar. E.g as the speed of light. Using it as a dimension of a problem is quite unintuitive.
>I’ve worked on ads at Meta, Snap, and Nextdoor. I also consult companies on building ads. If you are building your ad stack, feel free to reach out — let’s chat!
Hmmm
Not sure I get your point here
After careful consideration I think the point of aeve890 is that the advertisment industry sucks big time.
Is this not the stereotypical big tech employee everyone love to bash here when the topic of advertising comes out? I've read thousand of comments about the morality of people working in that industry. Well, here's one.
I hope it helps.
And actually, you can observe the values in action here:
Do we really need yet another blog post about Fourier transforms that's really just self-promotion on HN?
What self-promotion? This was posted to HN by someone who had a long history of posting lots of links, with no obvious connection to the writer of the blog post.
As for yet another Fourier related post, shall we talk about AI instead?