Understanding Discrete Fourier Transform
https://stackoverflow.com/questions/744596
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I have a small query regarding the discrete Fourier transforms. If I understand correctly, then what we do is convert a polynomial to its point value representation, with n points for a polynomial that goes up to the power of n-1. But why must we evaluate it at the nth roots of unity? Wouldn't any other n points uniquely identify this polynomial AND be much simpler?
Solution
Wouldn't any other n points uniquely identify this polynomial AND be much simpler?
No to both. 1) There's no guarantee that n arbitrary points would work and 2) it wouldn't be simpler. Turn the question around: why do you object to the roots of unity?
OTHER TIPS
The chief applicative reasons are
- Waves become monomials.
- Product on the time space is convolution on the phase space and vice versa (so you can multiply two polynomials of degree n in O(n log n) ).
- Derivative on the time space is product by x on the phase space and vice versa.
You'd have none of these with random points - intuitively speaking, because they do not form a group. There are many more theoretical reasons (and also a few more applicative ones)
No, not really. It's got nothing to do with polynomials. It's about decomposing a vector (the initial sequence of numbers) into a different basis. It's just that this basis has a series of very useful properties:
(1) It's orthogonal -- the vectors don't mix, and determining the transformation back to the original basis is exceedingly simple.
(2) The Fourier basis vectors are eigenvectors of the shift (or circular shift, for the discrete case) operation -- a Fourier basis function, after shifting the vector indices, is still the same function (times a number). That's what makes convolutions and the solution of a large class of differential equations very simple in Fourier space.
(3) And finally, the entries are roots of unity -- this gives raise to the FFT, one of the most elegant algorithms ever discovered, reducing the N^2 operations required for a change of basis to N log N.
Here are two "intuitive" explanations of the Discrete Fourier Transform. They do not jump into equations directly, but walk you through in a wish-someone-told-me-this-before way
