The Fourier Transform, explained in one sentence (Revolutions)

If, like me, you struggled to understand the Fourier Transformation when you first learned about it, this succinct one-sentence colour-coded explanation from Stuart Riffle probably comes several years too late:

Stuart provides a more detailed explanation here. This is the formula for the Discrete Fourier Transform, which converts sampled signals (like a digital sound recording) into the frequency domain (what tones are represented in the sound, and at what energies?). It's the mathematical engine behind a lot of the technology you use today, including mp3 files, file compression, and even how your old AM radio stays in tune.

The daunting formula involves imaginary numbers and complex summations, but Stuart's idea is simple. Imagine an enormous speaker, mounted on a pole, playing a repeating sound. The speaker is so large, you can see the cone move back and forth with the sound. Mark a point on the cone, and now rotate the pole. Trace the point from an above-ground view, if the resulting squiggly curve is off-center, then there is frequency corresponding the pole's rotational frequency is represented in the sound. This animated illustration (click to see it in action) illustrates the process:

The upper signal is make up of three frequencies ("notes"), but only the bottom-right squiggle is generated by a rotational frequency matching one of the component frequencies of the signal.

By the way, no-one uses that formula to actually calculate the Discrete Fourier Transform — use the Fast Fourier Transform instead, as implemented by the fft function in R. As the name suggests, it's much faster.

AltDevBlog: Understanding the Fourier Transform (note: updated link 20 Oct 2015 with active mirror)

Very interesting article, thank you. Please take a moment to rephrase the following key statement, if you would: "...then there is frequency corresponding the pole's rotational frequency is represented in the sound."

polar form e^iθ is equal to the rectangular form cosθ+isinθ and corresponds to the coordinates (cosθ,sinθ) such that
e^i0 = 1 = (1,0)
e^iτ/4 = i = (0,1)
e^iτ/2 = -1 = (-1,0)
e^iτ3/4 = -i = (0,-1)
e^iτ = 1 = (1,0)

May I suggest a minor exception to your claim about FFT: most modern languages, R included, use some variation of the "pure" 2^N Cooley-Tukey FFT algorithm as appropriate to support factors of 3, 5, etc. in the length of the dataset, and even default to the "raw" DFT for other data lengths (unless specifically suppressed by the user).
And, of course, the FFT is in fact that equation, just with gobs of like terms grouped together. :-)