Every time I think “Now I understand the Fourier Transform,” I am wrong.

Doing the Fourier Transform of a function is just seeing it from “another” point of view. The “usual” view of a function is in the standard basis . For example, can be seen as a vector (in the basis given by the elements in the domain) whose coordinates are the evaluations of on theĀ elements in the domain. It can also be seen as a polynomial (in the monomial basis) whose coefficients are these evaluations. Let us call this vector .

The same function can also be seen from the “Fourier basis”, which is just another orthogonal basis, formed by the basis vectors . The th coordinate in the new basis will be given by inner product between and the th basis vector . We call these inner products the Fourier coefficients. The Discrete Fourier Transform matrix (the DFT matrix) “projects” a function from the standard basis to the Fourier basis in the usual sense of projection: taking the inner product along a given direction.

In this post, I am going to use elementary group theoretic notions, polynomials, matrices, and vectors. The ideas in this post will be similar to this Wikipedia article on Discrete Fourier Transform.

Continue reading “Discrete Fourier Transform: the Intuition”