What are discrete and fast Fourier transform intuitively?

Solution 1:

So first things first: the FFT simply refers to the algorithm by which one may compute the DFT. So, if you understand the DFT, you understand the FFT as far as intuition goes (I think).

Now with the DFT, our goal is to write of $N$ points $x_0,x_1,...,x_{N-1}$ as the sum of complex exponentials. That is, we say that $X_n$ is the DFT of $x_n$ exactly when $$ x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot e^{(2 \pi i\, k\, n) / N} $$ You might recognize this as the inverse DFT of $X_n$. The key is that for each $k$, each $e^{(2 \pi i\, k\, n) / N}$ can be though of as a complex vector with $N$ entries. We could write $$ v_k=\left(\frac 1N,\frac1N e^{(2 \pi i\, k) / N},\frac1N e^{(4 \pi i\, k) / N},\dots,\frac1N e^{(2 \pi i\, k\, (N-1)) / N}\right) $$ There are $N$ vectors of this form (taking $k$ from $0$ to $N-1$), and we use them because they form an orthonormal basis of $\mathbb C ^N$. That is, $\langle v_k,v_j \rangle$ is $1$ if $k=j$ and $0$ if $k≠j$. Because these vectors are orthonormal, we can change basis (i.e. find the DFT) by using the dot product rather than by solving a system of $N$ equations.

That is, if $x=(x_0,x_1,\dots,x_{N-1})$ is the vector of complex entries of our time domain sequence, then $k^{th}$ entry the DFT of $x_0,x_1,\dots,x_{N-1}$ is simply given by $$ X_k = \langle x,v_k \rangle $$ and the IDFT is computed by finding $$ x = \sum_{k=0}^{N-1} X_k v_k $$ That is certainly my intuition for the computational process, and I find that helps. What this doesn't really help with is why we'd want to deal with complex exponentials in the first place, but if you've seen DFTs already I suppose you have some idea.

Solution 2:

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

http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/

http://www.altdevblogaday.com/2011/05/17/understanding-the-fourier-transform/

and for Fast Fourier Transform

http://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/

Solution 3:

The discrete Fourier transform is a linear operator on $\mathbb C^n$. The DFT simply changes basis to a special basis, the discrete Fourier basis. Each $n$th root of unity $\omega$ gives us a discrete Fourier basis vector $v = (1, \omega, \omega^2,\ldots,\omega^{n-1})$. It's immediate to check that $v$ is an eigenvector of the cyclic shift operator $S$, with eigenvalue $\omega$. Because $S$ preserves norms, $S$ is unitary, hence normal, so eigenvectors corresponding to distinct eigenvalues are orthogonal. Thus, once we normalize, we have an orthonormal basis.