View source for HowTo:Fourier

The Fourier transform is such a useful fundamental tool, it deserves its own howto (as opposed to a simple [[Code]]).  The Fourier transform is a transformation of a function into another function.  The transformation can (in almost all cases) be reversed.  

= Analogies =
Before getting started, a few analogies are helpful.

Sound comes from acoustic pressure waves -- so you hear middle C when your ear feels a time-varying pressure at precisely 261.6 Hz (1 Hz = 1 cycle per second).  The pressure signal would be <math>P(t) \propto cos(2 \pi (261.6 t))</math> -- so that 1/261.6 second goes in a complete cycle, from 0 to <math>2\pi</math> radians.  Fourier transforming that signal gives a function that is zero everywhere except for <math>k = 261.6</math> -- a delta function.  The transform of a pure sin or cos wave is always a delta function -- peaked at one particular frequency.  If you shift the phase of the sin or cos wave (say by <math>\Delta \theta = 2 \pi (261.6 \Delta t)</math>) this shows up in Fourier space as a phase factor, <math>\exp(i\Delta \theta)</math>, which does not change the magnitude.

Light comes from electromagnetic waves.  In parking lots, you can usually see the grungy yellow/orange color of 589.29 nm light from cheap high-pressure sodium lights.  This is because your eye is experiencing a time-varying electric field at a frequency of <math>3\cdot 10^{17}</math> nm/s / 589.29 nm <math>\simeq</math> 510 THz.

= Definition =
The Fourier transform of <math>f(x)</math> is defined as

<math> F(k) = \int_{-\infty}^\infty f(x) e^{-2\pi i k x} \; dx
</math>

You can immediately see why the Fourier transform of a pure wave, <math>f(x) = e^{2\pi i s x}</math>, is centered on <math>k = s</math>.  All the other test frequencies, <math>k</math>, create oscillatory integrands,

<math> e^{2\pi i (s - k) x}
</math>

so the integral always cancels, unless <math>s = k</math>, where it shoots to infinity (<math>F(k) = \delta(k-s)</math>).

The Fourier transform `picks up' all these pure frequencies.  You can see this by noting the transform of a bunch of pure waves,

<math> g(x) = \sum_j a_j e^{2\pi i k_j x}
</math>

which is a sum over all the pure frequencies,

<math>G(k) = \sum_j a_j \delta(k-k_j)
</math>

The reverse of the Fourier transform is just another Fourier transform.  This time, the direction of oscillation has to change, though:

<math> f(x) = \int_{-\infty}^\infty F(k) e^{2\pi i k x} \; dk
</math>

For visually understanding the Fourier transform, it's helpful to plot both sides of a table of transforms.  We already showed that the transform of a wave is a delta function, and vice-versa.  This means the transform of a constant is a delta function centered at zero.  As another example, the transform of a Gaussian function is another Gaussian function.

== Other Definitions ==

Note that there are other definitions of the Fourier transform.  These are all related to the above, by scaling <math>k \to \nu/a</math>, so

<math> F_a(\nu) = \int_{-\infty}^\infty f(x) e^{-\frac{2\pi}{a} i\nu x} \; dx
</math>

and

<math> f(x) = |a^{-1}| \int_{-\infty}^\infty F_a(\nu) e^{\frac{2\pi}{a} i\nu x} \; d\nu
</math>

Common variations are <math>a = -1</math> and <math>a = \pm 2\pi</math>.  Note that these formulas aren't applicable for imaginary <math>a</math>.  If you do that, you'll end up translating the Fourier theory into its equivalent -- analytic continuations of Laplace transforms and their inverse via Bromwich contours.

= Discrete Version =

The discrete Fourier transform is one limit of the continuous one, where the integral is replaced by the sum.  Before introducing this, however, it's helpful to introduce the Fourier transform on a circle.

<math> F_L(k) = \int_0^L f(x) e^{-2\pi i k x / L} \; dx
</math>

The integral runs over 0 to L, at which point the function is considered to be periodic -- i.e. <math>f(0) = f(L)</math>.  This definition is consistent with the `other definitions' above, for <math>a = L</math>.

Now, because the function is periodic, the test functions should be also.  This means we only need to collect the values of <math>F_L(k)</math> at integer values of <math>k = n = 0, \pm 1, \ldots</math>
-- those for which the test functions are periodic.
Conversely, given a finite set of frequency values, we can make good approximations of the function using the inverse Fourier transform,

<math> f(x) \simeq \sum_{n=-M/2}^{M/2} a_n e^{2\pi i n x / L}
</math>

Now we have a computational way to represent the Fourier transform -- a set of coefficients, <math>\{a_n\}_{-M/2}^{M/2}</math>.  Each coefficient belongs to a basis function -- called a `plane-wave' basis in physics because of its oscillation as <math>x</math> varies along the direction of travel of the wave.

To complete the picture, let's introduce a set of <math>M</math> equally spaced sampling points, <math>x_m/L = m / M</math>.  The inverse Fourier transform at these points is then a polynomial,

<math>f(x_m) \simeq \sum_{n=0}^{M} a_n \omega^{nm}
</math>

where <math>\omega = e^{2\pi i/M}</math>.  Moreover, given the set <math>f(x_m) = b_m</math>, the inverse
of the inverse is

<math>a_n \simeq \frac{1}{M}\sum_{m=0}^{M} b_m \omega^{-nm}
</math>

These last two are the discrete Fourier transform.  They are polynomials in the <math>M^{th}</math> roots of unity, <math>\omega</math>.

= Efficient DFT =

There are efficient ways of computing the discrete Fourier transform.  They derive from noting that <math>\omega^{n+M/2} = \omega^{-n}</math> (for even <math>M</math>).