Fourier transform for dummies What is the Fourier transform? What does it do? Why is it useful (in math, in engineering, physics, etc)?



This question is based on the question of Kevin Lin, which didn't quite fit in Mathoverflow. Answers at any level of sophistication are welcome.
The ancient Greeks had a theory that the sun, the moon, and the planets move around the Earth in circles.  This was soon shown to be wrong.  The problem was that if you watch the planets carefully, sometimes they move backwards in the sky.  So Ptolemy came up with a new idea - the planets move around in one big circle, but then move around a little circle at the same time.  Think of holding out a long stick and spinning around, and at the same time on the end of the stick there's a wheel that's spinning.  The planet moves like a point on the edge of the wheel.

Well, once they started watching really closely, they realized that even this didn't work, so they put circles on circles on circles...  

Eventually, they had a map of the solar system that looked like this:



This "epicycles" idea turns out to be a bad theory.  One reason it's bad is that we know now that planets orbit in ellipses around the sun.  (The ellipses are not perfect because they're perturbed by the influence of other gravitating bodies, and by relativistic effects.)

But it's wrong for an even worse reason that that, as illustrated in this  wonderful youtube video.

In the video, by adding up enough circles, they made a planet trace out Homer Simpson's face.  It turns out we can make any orbit at all by adding up enough circles, as long as we get to vary their size and speeds. 

So the epicycle theory of planetary orbits is a bad one not because it's wrong, but because it doesn't say anything at all about orbits.  Claiming "planets move around in epicycles" is mathematically equivalent to saying "planets move around in two dimensions".  Well, that's not saying nothing, but it's not saying much, either!

A simple mathematical way to represent "moving around in a circle" is to say that positions in a plane are represented by complex numbers, so a point moving in the plane is represented by a complex function of time.  In that case, moving on a circle with radius $R$ and angular frequency $\omega$ is represented by the position

$$z(t) = Re^{i\omega t}$$

If you move around on two circles, one at the end of the other, your position is 

$$z(t) = R_1e^{i\omega_1 t} + R_2 e^{i\omega_2 t}$$

We can then imagine three, four, or infinitely-many such circles being added.  If we allow the circles to have every possible angular frequency, we can now write

$$z(t) = \int_{-\infty}^{\infty}R(\omega) e^{i\omega t} \mathrm{d}\omega.$$

The function $R(\omega)$ is the Fourier transform of $z(t)$.  If you start by tracing any time-dependent path you want through two-dimensions, your path can be perfectly-emulated by infinitely many circles of different frequencies, all added up, and the radii of those circles is the Fourier transform of your path.  Caveat: we must allow the circles to have complex radii.  This isn't weird, though.  It's the same thing as saying the circles have real radii, but they do not all have to start at the same place.  At time zero, you can start however far you want around each circle.

If your path closes on itself, as it does in the video, the Fourier transform turns out to simplify to a Fourier series.  Most frequencies are no longer necessary, and we can write

$$z(t) = \sum_{k=-\infty}^\infty c_k e^{ik \omega_0 t}$$

where $\omega_0$ is the angular frequency associated with the entire thing repeating - the frequency of the slowest circle.  The only circles we need are the slowest circle, then one twice as fast as that, then one three times as fast as the slowest one, etc.  There are still infinitely-many circles if you want to reproduce a repeating path perfectly, but they are countably-infinite now.  If you take the first twenty or so and drop the rest, you should get close to your desired answer.  In this way, you can use Fourier analysis to create your own epicycle video of your favorite cartoon character.

That's what Fourier analysis says.  The questions that remain are how to do it, what it's for, and why it works.  I think I will mostly leave those alone.  How to do it - how to find $R(\omega)$ given $z(t)$ is found in any introductory treatment, and is fairly intuitive if you understand orthogonality.  Why it works is a rather deep question.  It's a consequence of the spectral theorem.

What it's for has a huge range.  It's useful in analyzing the response of linear physical systems to an external input, such as an electrical circuit responding to the signal it picks up with an antenna or a mass on a spring responding to being pushed.  It's useful in optics; the interference pattern from light scattering from a diffraction grating is the Fourier transform of the grating, and the image of a source at the focus of a lens is its Fourier transform.  It's useful in spectroscopy, and in the analysis of any sort of wave phenomena.  It converts between position and momentum representations of a wavefunction in quantum mechanics.  Check out this question on physics.stackexchange for more detailed examples.  Fourier techniques are useful in signal analysis, image processing, and other digital applications.  Finally, they are of course useful mathematically, as many other posts here describe.
Fast Fourier Transform is used in Engineering to reduce Computation time for solving Matrix Algebraic Equations and Matrix Difference Equations.