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.

Solution 1:

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.

Solution 2:

It took me quite a while to understand what exactly is meant by Fourier transform since it can refer to various algorithms, operations and results. Though I'm quite new in this topic, I'll try to give a short but hopefully intuitive overview on what I came up with (feel free to correct me):

Let's say you have a function $f(t)$ that maps some time value $t$ to some value $f(t)$.

Now we'll try to approximate $f$ as the sum of simple harmonic oscillations, i.e. sine waves of certain frequencies $\omega$. Of course, there are some frequencies that fit well to $f$ and some that approximate it less well. Thus we need some value $\hat{f}(\omega)$ that tells us how much of a given oscillation with frequency $\omega$ is present in the approximation of $f$.

Take for example the red function from here

which is defined as

$$f(t) = \sin(t)+0.13\sin(3t)$$

The green oscillation with $\omega=1$ has the biggest impact on the result, so let's say $$\hat{f}(1)=1$$

The blue sine wave ($\omega=3$) has at least some impact, but it's amplitude is much smaller. Thus we say $$\hat{f}(3)=0.13$$

Other frequencies may not be present in the approximation at all, thus we would write $$\hat{f}(\omega) = 0$$ for these.

Now if we knew $\hat{f}(\omega)$ not only for some but all possible frequencies $\omega$, we could perfectly approximate our function $f$. And that's what the continuous Fourier transform does.

It takes some function $f(t)$ of time and returns some other function $\hat{f}(\omega) = \mathcal{F}(f)$, its Fourier transform, that describes how much of any given frequency is present in $f$. It's just another representation of $f$, of equal information but with a completely different domain. Often though, problems can be solved much easier in this other representation (which is like finding the appropriate coordinate system).

But given a Fourier transform, we can integrate over all frequencies, put together the weighted sine waves and get our $f$ again, which we call inverse Fourier transform $\mathcal{F}^{-1}$.

Now why should one want to do that?

Most importantly, the Fourier transform has many nice mathematical properties (i.e. convolution is just multiplication). It's often much easier to work with the Fourier transforms than with the function itself. So we transform, have an easy job with filtering, transforming and manipulating sine waves and transform back after all.

Let's say we want to do some noise reduction on a digital image. Rather than manipulating a function $\text{image} : \text{Pixel} \to \text{Brightness}$, we transform the whole thing and work with $\mathcal{F}(\text{image}) : \text{Frequency} \to \text{Amplitude}$. Those party of high frequency that cause the noise can simply be cut off - $\mathcal{F}(\text{image})(\omega) = 0, \omega > ...Hz$. We transform back et voilà.