# Fourier transform for dummies

A vague question of Kevin Lin which didn't quite fit at Mathoverflow:

So ... what is the Fourier transform? What does it do? Why is it useful (both in math and in engineering, physics, etc)?

(Answers at any level of sophistication are welcome.)

-
When I was learning about FTs for actual work in signal processing, years ago, I found R. W. Hamming's book Digital Filters and Bracewell's The Fourier Transform and Its Applications good intros to the basics. Strang's Intro. to Applied Math. would be a good next step. Do a discrete finite FT by hand of a pure tone signal over a few periods to get a feel for the matched filtering and the relation of constructive and destructive interference to orthogonality. –  Tom Copeland May 9 '12 at 6:29
Here's a neat post breaking down the Fourrier transform. –  Hakim Mar 23 '14 at 15:12
I used this book to both learn calculus and the Fourier transform in high school. It was outstanding. –  Zack Angelo Mar 25 '14 at 20:53
Here's a video I made a while ago describing the fourier series and fourier transform. It's a bit of a light hearted approach. youtube.com/watch?v=Qm84XIoTy0s –  Carl Mar 26 '14 at 7:11

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 the 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.

-
This paper's quite relevant. –  Guess who it is. Dec 17 '11 at 9:39
So. Freaking. Cool. –  AndrewG Oct 25 '12 at 23:33
This is possibly the most illuminating thing I've read in weeks. Wonderful! –  icurays1 Nov 12 '13 at 18:50
Hi, I have written my own article about FT, how do I understand it - blog.ivank.net/fourier-transform-clarified.html . The idea of "circle on circle on circle" is probably the best way to look at it :) –  Ivan Kuckir Aug 15 '14 at 15:21
This is just a brilliant answer +1 –  Mike Miller Jan 1 at 2:24

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à.

-
good illustration, but I think image is function in spatial domain, not time domain, right? How does Fourier transform work on it? –  loganecolss Aug 11 '13 at 3:11
@loganecolss it's easier to understand fourier transform with an example on time domain. but of course it's not limited on domain of the problem. let image is a function over spatial domain resulting a color of given point. –  Burak SARICA Mar 26 '14 at 13:12

Let me partially steal from the accepted answer on MO, and illustrate it with examples I understand:
The Fourier transform is a different representation that makes convolutions easy.
Or, to quote directly from there: "the Fourier transform is a unitary change of basis for functions (or distributions) that diagonalizes all convolution operators." This often involves expressing an arbitrary function as a superposition of "symmetric" functions of some sort, say functions of the form eitx — in the common signal-processing applications, an arbitrary "signal" is decomposed as a superposition of "waves" (or "frequencies").

### Example 1: Polynomial multiplication

This is the use of the discrete Fourier transform I'm most familiar with. Suppose you want to multiply two polynomials of degree n, given by their coefficients (a0, …, an) and (b0, …, bn). In their product, the coefficient of xk is ck = ∑aibk-i. This is a convolution, and doing it naively would take O(n2) time.

Instead, suppose we represent the polynomials by their values at 2n points. Then the value of the product polynomial (the one we want) at any point is simply the product of the values of our original two polynomials. Thus we have reduced convolution to pointwise multiplication. The Fourier transform and its inverse correspond to polynomial evaluation and interpolation respectively, for certain well-chosen points (roots of unity). The Fast Fourier Transform (FFT) is a way of doing both of these in O(n log n) time.

### Example 2: Convolution of probability distributions

Suppose we have two independent (continuous) random variables X and Y, with probability densities f and g respectively. In other words, P(X ≤ x) = ∫x-∞ f(t)dt and P(Y ≤ y) = ∫y-∞ f(t)dt. We often want the distribution of their sum X+Y, and this is given by a convolution: P(X+Y ≤ z) = ∫f(t)g(z-t)dt. This integration may be hard.

But instead of representing the random variables by their densities, we can also represent them by their characteristic functions φX(t) = E[eitX] and φY(t) = E[eitY]. Then the characteristic function of X+Y is just:
φX+Y(t) = E[eit(X+Y)] = φX(t)φY(t) since they're independent. The characteristic function is the continuous Fourier transform of the density function; it is a change of representation in which convolution becomes pointwise multiplication.

To quote again the answer on MO, many transformations we want to study (translation, differentiation, integration, …) are actually convolutions, so the Fourier transform helps in a wide number of instances.

-

Think about light coming from stars.

The light has colour or "spectrum" but of course the data comes in a 1-D stream.

The Fourier transform gives you the spectrum of the time series.

You can also think about the EQ on your stereo -- the 2kHz slider, the 5kHz slider, etc. Those sliders are adjusting the constants in a Fourier-like realm. (see @leonbloy's caveats below)

(Inverse Fourier just takes you back from spectrum to signal. So what does it mean that $\mathcal{F}^{-1} = \mathcal{F}$?)

To get into the maths of it, remember that $\cos$ and $\sin$ are just phase-shifted versions of one another. Mathematically, you add together different amounts (amplitudes) of various phase-shifted $\sin$ waves and it's a surprising fact that doing so can add up to any function.

(How would you get a straight line like $y={1 \over 3} x$ for example?)

note: The transformed series don't have to be a time series exactly. You could parametrize lots of curves by $t$. For example handwriting or the outline of dinosaur footprints.

Why is it useful in physics? One use is to express the definitiveness of Heisenberg uncertainty. A given wavefunction $\Psi$ in space (position) can be $\mathcal{F}(\Psi)$ to time (momentum). Since the time-space conversion is bijective, position & momentum (anti)covary i.e. you can't increase one without decreasing the other. Frank Wilczek makes use of $\mathcal{F}$ in this video explaining QCD for example.

How is it used in engineering? Signal processing, image processing (PDF, jump to page 5), and video processing use the Fourier basis to represent things.

-
hint. the answer to the second puzzle involves limits. –  isomorphismes Mar 24 '11 at 1:23
One caveat: in most uses, a "spectrum" (including the EQ) measures the enery per frequency, which relates to the absolute value of the Fourier transform. That is "a part" of the Fourier transform (you lack the "phase"), and hence, from the spectrum you cannot get back the signal. (A second caveat would related to the fact that the EQ measures a time-windowed spectrum, which varies on time; the Fourier transform does not depend on time). –  leonbloy Oct 14 '11 at 2:02
@leonbloy Thanks for the correction. And I guess real-world signals also do not extend infinitely left or right which is discussed in first lecture about lasers. I found from that lasers are understood much better by someone understands $\mathcal{F}$. –  isomorphismes Jan 4 '13 at 8:24
That second figure (the one with the inset protein) looks like a mass spectrum. Most MS detection methods obtain a spectrum directly from a time-domain signal, although there are exceptions like fourier transform ion cyclotron resonance –  Richard Terrett Mar 26 '14 at 1:49
That's right @RichardTerrett. That image isn't really so good as what I really wanted was elemental decomposition on stars, not proteins. Thanks fro pointing out the shortcoming. –  isomorphismes Mar 28 '14 at 3:59

If you have a time series that you think is the result of a additive collection of periodic function, the Fourier transform will help you determine what the dominant frequencies are.

This is the way guitar tuners work. The perform and FFT on the sound data and pick out the frequency with the greatest power (squares of the real and imaginary parts) and consider that the "note." This is called the fundamental frequency.

There are many other uses, so you might want to add big list as a tag.

-
I interpreted the question as asking "explain why this is useful," rather than "list some examples of its use." Only the latter would deserve a big-list tag. –  Larry Wang Jul 28 '10 at 20:31

You could think of a Fourier series expanding a function as a sum of sines and cosines analogous to the way a Taylor series expands a function as a sum of powers.

Or you could think of the Fourier series as a change of variables. A fundamental skill in engineering and physics is to pick the coordinate system that makes your problem simplest. Since the derivatives of sines and cosines are more sines and cosines, Fourier series are the right "coordinate system" for many problems involving derivatives.

-

One of the best explanation I've stumbled upon is the following one on betterexplained: http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/ and also : http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-homer-simpsons-face

-
+1 For better explained. I read tons of 'fourier transform' guides before I found this one. –  Thomas Ahle Mar 25 '14 at 21:26

Here's some simple Matlab code to play around with if you like.


% This code will approxmmate the function f using the DFT

clear all
close all

a=0;b=2*pi; % define interval, i.e. endpoints of domain(f)

N=20; % number of sample points to take from f

% build vector of points in domain(f) to sample from
for j=1:N+1
x(j) = (b-a)*(j-1)/N;
end

f= cos(x); % approximate cos(x) with resulting Fourier series

% build matrix of powers of roots of unity
for m=1:N+1
for n=1:N+1
F(m,n) = exp((m-1)*(n-1)*(2*pi*i)/N);
end
end

% solve f = Fc by domng F\f
c = F\f'; % c is vector of Fourier coefficients

% plot discrete cos(x) using N points

xx=0:0.01:2*pi;
plot(xx,cos(xx),'g')
hold on

% build the Fourier series using coefficients from c
summ=0;
for k=1:length(c)
summ = summ + c(k)*exp(i*(k-1)*x);
end

% plot the fourier series against the discrete sin function
plot(x,summ)
legend('actual','approx.')




As written you will have the first N=20 terms of the Fourier approximation to the cosine on the interval [a,b]=[0,2*pi]. Not very interesting as is...

Reference: Gilbert Strang.

-
+1 for the MATLAB code –  draks ... Jan 21 '13 at 12:47

I'm in a calc 2 class and the Fourier Series are sort of the crowning achievement of the class. Still, I had a hard time figuring out what it was used for. From what I know, and I could be wrong, signals or sin/cos waveforms can be additive or subtractive. So if you take a look at the picture at the top of the page, you'll see a green and blue signal. Well that's all well and good, but what happens if you add them together? Their periods are different, so it's not going to result in just an average of the two forms. So you end up with the red line. It's y value is large like the green, but it's period is smaller than that of the green. The top and bottom look more like the blue line. So this is what a fourier series does. It takes two signals and puts them together to make a new signal. With more and more signals added together, you can approach very specific wave forms, like a square wave or a saw tooth wave (triangular). It's not perfect though, and the difference between green and red waves can be explained with the Gibbs Phenomenon. I hope this helps.

-

The Fourier transform returns a representation of a signal as a superposition of sinusoids. Fourier transforms are used to perform operations that are easy to implement or understand in the frequency domain, such as convolution and filtering. If the signal is well-behaved, one can transform to and from the frequency domain without undue loss of fidelity.

-

Here is my understanding of the Fourier transform as it came to me.

Imagine you have an object that makes some sound when it is jolted (e.g. a drinking glass, tuning fork, cymbal, guitar string, you name it). Any sound made this way is a composition of several frequencies (it's only a perfect hemisphere that vibrates in a true harmonic wave). I now want to analyze the frequencies present in that sound, and I want to do it the old-fashioned way.

I put the object somewhere where it's free to oscillate and make sound. Next I play a pure tone in some frequency to it, and measure how much it moves in unison. If it moves a lot in unison, then there should be a lot of that frequency in its natural sound. This is what the Fourier transform does, only with functions.

In general, the Fourier transform of a function $f$ is defined by $$\hat f(\omega) = \int_{-\infty}^\infty f(z)e^{-2\pi i\omega z}dz$$ The exponential term is a circle motion in the complex plane with frequency $\omega$. It plays the role of the pure tone we played to the object. The reason we use a complex exponential term instead of a pure trigonometric term is that with a $\sin$ term we could be unlucky with the phase. This way we get a result with the same absolute value no matter the phase, only the direction of $\hat f(\omega)$ will vary.

If $f$ has a lot of $\omega$-frequency oscillation in it, then the numbers $f(z)e^{-2\pi i \omega z}$ will tend to line up in the same general direction in the complex plane for different $z$ (exactly what direction that is depends on the phase, as noted above). As you integrate over $z$, $\hat f(\omega)$ becomes relatively large.

On the other hand, if $f$ doesn't have much $\omega$-frequency oscillation in it, then the integrand will end up on all sides of the origin for different $z$, and as you integrate, the result $\hat f(\omega)$ will be small.

-

A more complicated answer (yet it's going to be imprecise, because I haven't touched this in 15 years...) is the following.

In a 3-dimentional space (for example) you can represent a vector v by its end point coordinates, x, y, z, in a very simple way. You choose three vectors which are of unit length and orthogonal with each other (a base), say i, j and k, and calculate the coordinates as such:

x = vi

y = vj

z = vk

In multidimentional space, the equations still hold. In a discrete infinite space, the coordinates and the base vectors become a sequence. The dot product becomes an infinite sum.

In a continuous infinite space (like the space of good functions) the coordinates and the bases become functions and the dot product an infinite integral.

Now, the Fourier transform is exactly this kind of operation (based on a set of base functions which are basically a set of sines and cosines). In other words, it is a different representation of the same function in relation to a particular set of base functions.

As a consequence, for example, functions of time, represented against functions of time and space (in other words integrated over time multiplied by functions of space and time), become functions of space, and so on.

Hope it helps!

-
The Fourier transform is a much more specific operation than this. The basis you choose is very special, and explaining why the Fourier transform is interesting should involve explaining that choice of basis. –  Qiaochu Yuan Jul 28 '10 at 19:53
I said it would be imprecise... however it's a "for dummies" question, no? –  Sklivvz Jul 28 '10 at 19:59
I agree with Qiaochu, this answer is too vague to be useful. –  Larry Wang Jul 28 '10 at 20:12
@Sklivvz: I didn't downvote this, but the point is that your answer just explains what a change of basis is, not what's special about the Fourier transform. –  ShreevatsaR Jul 28 '10 at 21:20
My point was that a Fourier transform is a change of basis (which is what I personally find interesting about it) - which in turn (in my humble opinion) totally answers the question... but then again the whole point of this site is that one says what he thinks and then the opinion of others values the answer. So, fair enough. =) –  Sklivvz Jul 28 '10 at 21:47

Starting from the discrete fourier transform: If you look at the Vandermonde matrix and the DFT matrix side by side, you notice that the DFT is a (suitably scaled) special Vandermonde matrix. You just insert the roots of unity into the values that appear in the Vandermonde matrix.

The main application of the Vandermonde matrix is polynomial interpolation. It follows that one interpretation of the DFT is that for a set of values it gives you the polynomial coefficients of the polynomial that maps the roots of unity to these values.

-

## protected by Asaf KaragilaNov 12 '13 at 18:44

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.