# Understanding Discrete and Fast Fourier Transform intuitively

I have done both of these in my math courses, but without understanding what they actually are intuitively. I would be very much grateful if you could give me an intuitive explanation of them.

-
Have you taken a course in linear algebra yet? I think of the terms $e^{\frac{2\pi i}{N}}$ as an orthogonal basis for $\mathbb C^N$, and I find that a little more intuition-friendly. – Omnomnomnom Jun 26 '13 at 13:57
I know this. But this is about representation of a function by complex exponentials. I don't have a clear idea about what the transforms (discrete and fast-fourier) actually are. – math Jun 26 '13 at 14:00
But the discrete Fourier transform is exactly that; a representation of a function by complex exponentials (or real sinusoids). Is that connection not clear? – Omnomnomnom Jun 26 '13 at 14:04
not clear. can you elaborate on that? – math Jun 26 '13 at 14:05
Sure. By the way, before I proceed: you mean the DFT and not the DTFT, right? – Omnomnomnom Jun 26 '13 at 14:06

## 3 Answers

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.

-
Thank you very much for making effort to put up this; it certainly gave me some intuition. I will accept this as final answer if I don't get any better replies. – math Jun 26 '13 at 18:55

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 $1/\omega = \bar{\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.

-

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/

-