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.
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 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
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.
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.
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.
>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!
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.
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?
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 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.
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 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
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.
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.
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.
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.
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.
>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
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.
After careful consideration I think the point of aeve890 is that the advertisment industry sucks big time.
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?