I like the linear algebra interpretation, where the DFT is a basis change, and the only 'magic' is believing/proving that the Fourier basis is orthogonal. (It's an easy proof.)
I still don't understand how the FFT works though...
If you understand DFT, it should be very easy to understand FFT. It's the same thing but with an infinite-dimensional vector space. The fact that it's a vector space is the important thing. The infinite dimensionality is relatively a minor detail.
No that's not right. The FFT is not infinite dimensional. It's the same dimension as whatever length FFT you take. The FFT is just a set of algorithms for computing the DFT. In general they work by recursively decomposing an N-length DFT into shorter length DFT's.
The DTFT on the other hand is "infinite" dimensional in that it takes an infinite time series as input and outputs a continuous spectrum with period of 2pi.
I like the linear algebra interpretation, where the DFT is a basis change
Yea. Maybe a loose analogy would be transforming from RGB to HSV space - the difference in how we can interpret the numbers in one versus the other is what's great.
Comments
I like the linear algebra interpretation, where the DFT is a basis change, and the only 'magic' is believing/proving that the Fourier basis is orthogonal. (It's an easy proof.)
I still don't understand how the FFT works though...
If you understand DFT, it should be very easy to understand FFT. It's the same thing but with an infinite-dimensional vector space. The fact that it's a vector space is the important thing. The infinite dimensionality is relatively a minor detail.
No that's not right. The FFT is not infinite dimensional. It's the same dimension as whatever length FFT you take. The FFT is just a set of algorithms for computing the DFT. In general they work by recursively decomposing an N-length DFT into shorter length DFT's.
The DTFT on the other hand is "infinite" dimensional in that it takes an infinite time series as input and outputs a continuous spectrum with period of 2pi.
Sorry, This is embarrassing, I must have not drank my coffee... Of course you are right.
I was talking about the O(n log n) algorithm that computes the DFT.
Yeah, see my other comment.
Yea. Maybe a loose analogy would be transforming from RGB to HSV space - the difference in how we can interpret the numbers in one versus the other is what's great.