Discrete Fourier Transform (nima101.github.io)

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.

>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

Feels like an article wrote from somebody who knows a lot about the FFT for people who already knows a lot about the FFT.

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.

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.

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.

TeX tip: it's \log, not log (ditto sin, cos, etc)

How much is fft used for AI? Seems that attention and convolution could benefit from this.

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...