Understanding DFT and FFT

When you took calculus, you learned that functions can be written in a kind of "Taylor series":

f(x) = a0 + a1 x + a2 x^2 + ...

However, the functions {1, x, x^2, ...} aren't unique. You can use any basis functions. Let's replace them with {Φ0, Φ1, Φ2, ...}. To find your "Taylor series" you need some way to measure how far off your approximation is. We call this an "inner product", and one common one is the integral, i.e.

<f, g> = integral of f̅g dx

If we can change our coefficients {ai} and get a better approximation, it means there is some basis function where

<Φi, f> =/= <Φi, a0Φ0 + a1Φ1 + a2Φ2 + ...> = a0<Φi, Φ0> + a1<Φi, Φ1> + a2<Φi, Φ2> + ...

So, to get the best approximation, we just set the left and right sides of the equation equal. This is really easy to calculate if most of the <Φi, Φj> = 0 (and cancel out). We call a basis orthogonal if <Φi, Φj> = 0 except when i=j. For an orthogonal basis, we're left with

<Φi, f> = ai<Φi, Φi> --> ai = <Φi, Φi> / <Φi, f>.

One common orthogonal basis are the Legendre polynomials, which are the same as {1, x, x^2, ...} with the Gram-Schmidt process applied to them. We're not really going to discuss those here. Another common one are sines and cosines. In trigonometry you learned that

e^{ix} = cos(x) + i sin(x),

so we can instead use the basis

{..., e^{-2ix}, e^{-ix}, 1, e^{ix}, e^{2ix}, ...}

Plugging this in gives the Fourier transform:

a_k = 1/2pi * integral from -pi to pi of e^{-kix}f(x) dx.