Fourier transform for dummies

Question

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.

Answer 1

I'll give an engineering answer.

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.

Answer 2

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.

Answer 3

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 = v ∙ i

y = v ∙ j

z = v ∙ k

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!

Answer 4

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.

Answer 5

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 e^itx — 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 (a₀, …, a_n) and (b₀, …, b_n). In their product, the coefficient of x^k is c_k = ∑a_ib_k-i. This is a convolution, and doing it naively would take O(n²) 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[e^itX] and φ_Y(t) = E[e^itY]. Then the characteristic function of X+Y is just:
φ_X+Y(t) = E[e^it(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.