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.
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à.
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").
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.
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.
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.
big-list tag.
$\endgroup$
Jul 28, 2010 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 : https://nautil.us/the-math-trick-behind-mp3s-jpegs-and-homer-simpsons-face-234629/
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.
I think the ideas are most clear in the case of the discrete Fourier transform, which can be understood very well with nothing but finite-dimensional linear algebra.
Here is a summary of how one might discover the discrete Fourier transform. Let $S$ be the cyclic shift operator on $\mathbb C^N$ defined by $$ S \begin{bmatrix} x_0 \\ x_1 \\ \vdots \\ x_{N-1} \end{bmatrix} = \begin{bmatrix} x_1 \\ \vdots \\ x_{N-1} \\ x_0 \end{bmatrix}. $$ A linear operator $A:\mathbb C^N \to \mathbb C^N$ is said to be "shift-invariant" if $A(Sx) = S(Ax)$ for all $x \in \mathbb C^N$. (So, if you shift the input, then the output simply gets shifted the same way). More concisely, $A$ is shift invariant if and only if $AS = SA$. In other words, a shift-invariant linear operator is one that commutes with the shift operator $S$.
Because shift-invariant operators are very important in signal processing and numerical analysis, we would like to understand them as well as possible. And one of the best ways to understand a linear operator is to find a basis of eigenvectors for it. In linear algebra, there are various "simultaneous diagonalization" theorems which state that, under certain assumptions, linear operators which commute can be simultaneously diagonalized. This suggests a strategy for diagonalizing a shift-invariant linear operator $A$. Because $A$ commutes with $S$, we can first find a basis of eigenvectors for $S$. Then, we can (hopefully) invoke a simultaneous diagonalization theorem to show that this basis of eigenvectors for $S$ is also a basis of eigenvectors for $A$.
Note that $S$ preserves norms, so it is unitary. Every unitary operator is normal. Thus, the spectral theorem guarantees that $S$ has an orthonormal basis of eigenvectors. Moreover, you could easily find the eigenvectors of $S$ by hand right now. After a short (and fun) calculation, you would discover that if $\omega$ is an $N$th root of unity then the vector $$ v_\omega = \begin{bmatrix} 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1} \end{bmatrix} $$ is an eigenvector of $S$. And what's the eigenvalue? Go ahead and shift $v_\omega$ right now, and you'll see the eigenvalue immediately. It's $\omega$, right? That was fun!
Because there are $N$ distinct $N$th roots of unity, we have found $N$ distinct eigenvalues and corresponding eigenvectors for $S$. And in fact, there is a simultaneous diagonalization theorem which says that because the eigenvalues of $S$ are distinct, any linear operator $A$ that commutes with $S$ is diagonalized by the same eigenvectors.
We have now discovered how to diagonalize any shift-invariant linear operator. The basis of eigenvectors we have discovered is called the "discrete Fourier basis". The "discrete Fourier transform" is simply the linear transformation that changes basis from the standard basis to the discrete Fourier basis.
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.
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.
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!
Fast Fourier Transform is used in Engineering to reduce Computation time for solving Matrix Algebraic Equations and Matrix Difference Equations.