Fourier transform

Every periodic function ('wave') can be interpreted (uniquely!) as the weighted sum of elementary waves (sines and cosines) of different frequencies. An infinite number of frequencies may be required to describe the wave in full.

The Fourier transform is the function that describes this interpretation. It transforms a function mapping time to amplitude (running from 0 to the function's period) to the corresponding function mapping frequency to frequency strength.

Efficient methods to compute it are known as FFT ('fast Fourier transform').

Many subsets of Fourier transforms are useful in compression. For example, JPEG, MPEG-1 and MPEG-2^*, MJPEG, and many other CODECs work based on DCTs, which are a simplified subset of FFTs. (MPEG-4 also supports all of MPEG-1 and MPEG-2, but primarily uses a bunch of other compression mechanisms for its various layers, mostly wavelet and procedural, rather than DCTs.) Basically only the most dominant waves are stored, and their characteristics are compressed using Huffman or similar. This technique is known as lossy compression, since only the most dominant details are preserved (which are usually the most important, but this leads to problems with medical images being transmitted by people who don't understand that JPEG loses a LOT of fine detail).

^* Contrary to popular belief, MP3 is not MPEG-3 (which doesn't exist); it's part of MPEG-1. MP3 gets its name from its common file extension, which is derived from it being MPEG-1 audio layer 3. Many low-bitrate so-called-MP3s are also actually compressed using layer 2. Unfortunately, when people see an MPG file they think movie, just like how when they see a WAV they think sound, even though both formats are multi-chunk, multi-layer, and multi-talented. In fact, the reference implementation of the MPEG-1 Layer 3 CODEC puts the audio chunk into a WAV file, rather than an MPEG file, because that's a more proper way to do it (and yet, most programs out there are lazy, as are most people when it comes to understanding these things, but the whole point to the WAV and MPG et al formats is so that people don't have to know the difference, since it's supposed to be up to the programs to grok this). (This has been a MaggieRant(tm). Consider yourself better-informed for digging around in completely-unrelated topics. :)

The Fourier Transform is an extremely important tool in applied mathematics. It appears in electro-dynamics, the study of waves, and quantum mechanics, and has strong links with Green's functions. It is also extremely useful in pure mathematics, as it can be used to prove the existence of solutions to certain classes of differential equations.

The Fourier Transform is closely linked to the Fourier Series. The Fourier Series allows us to express periodic functions as discrete sums of sine waves, while the Fourier Transform allows us to express any function a continuous integral of sine waves.

Definition

For a complex function f(x) which satisfies the condition that

integral(|f(x)|dx, x=-inf...inf)

takes a finite value, the Fourier Transform F(k) is given by

F(k)= 1/sqrt(2π) integral(f(x)exp(-ikx)dx, x=-inf...inf).

Comments

The function F is often denoted as f with a tilde ("~"). We think of F(k) as a representation of f in Fourier space, which is dual to normal space. In applied mathematics the factor of 1/sqrt(2π) is omitted: since we never directly compare f(x) and F(k) it is seldom needed. Because the integral is from negative infinity to positive infinity, the techniques of contour integration, particularly Jordan's lemma, are often useful.

There is a corresponding vector result: if f(x) is a function on n dimensions, then it has Fourier Transform

F(ξ) = (2π)n/2 integral(f(x)exp(-i x.ξ)dx, x in Rn).

Basic properties

From the definition, we can prove the following basic results, which are useful when manipulating Fourier expressions.

1. Linearity. Let h(x) = f(x) + g(x). Then H(k) = F(k) + G(k).
2. Translation. Let g(x) = f(x-a). Then G(k) = exp(-ika) F(k).
3. Frequency shift. Let g(x) = exp(ilx) f(x). Then G(k) = F(k-l).
4. Scaling. Let g(x) = f(ax). Then G(k) = F(k/a)/|a|.
5. Derivative. Let g(x) = f'(x). Then G(k) = ik F(k).
6. Factors of x. Let g(x) = xf(x). Then G(k) = i dF(k)/dk.

These results are easily proved using the properties of integration. Note the duality of the results 2 and 3, and of the results 5 and 6. The fifth result is critical in many applications of Fourier Transforms since it allows us to rewrite differential equations in a form without derivatives. For example, consider the differential equation

f''(x) - 5f'(x) + 6f(x) = g(x)

where we wish to find f(x) for an arbitrary input function g(x). Then in the Fourier representation we have

-k2 F(k) - 5 ik F(k) + 6 F(k) = G(k)
F(k) = G(k) / (6 - 5ik - k2).

Using Fourier Transforms we now have an expression linking f and g not involving any derivatives.

Inversion

Suppose F(k) is the Fourier Transform of f(x). Then if f is continuous we have the Inverse Fourier Transform

f(x) = 1/sqrt(2π) integral(exp(ikx)F(k)dk, k=-inf...inf).

If f is discontinuous at x, then we have the more general result

(f(x+) + f(x-))/2 = 1/sqrt(2π) integral(exp(ikx)F(k)dk, k=-inf...inf),

where f(x₊) and f(x_-) represent the values of f on either side of the discontinuity.

Fourier transforms are very important for a variety of spectrocopic techniques, for example NMR and infrared spectroscopy. Before computers were suffiecently powerful to handle the algorithm quickly enough, all measurements were done in a continuous wave mode. The difference between the two methods FT and CW, can be illustrated as follows :-

Say you've made a church bell, it's overall tone will be made up of a variety of frequencies and harmonics; how good the bell sounds depends of the exact amplitude of each frequency produced. You could quantify all this by making measurements of the bell's performance....

One way to do this would be to take a frequency generator, loudspeaker and a microphone. You would put the speaker and the microphone inside the bell, and then generate discrete frequencies across the whole range you might expect to get a response and play them through the speaker. You use the microphone to measure the bells response at each frequency, plotting the amplitude response on graph paper as you go. This would give you a spectrum, characteristic of the bell. Note to make very fine measurements, you have to sweep very carefully, like trying to tune into one of two very close FM radio statons, which takes time. Also the amplitude of the signals may be very weak, so sensitive equipment may be needed.

A far better way is to just take the microphone, stick it in the bell, and whack the bell with a hammer! Now the output will be a very complicated waveform, consisting of all the frequencies the bell can produce, decaying over time. The fourier transform can take this time based information and convert it back to the frequency domain to give the same result as above. The free inductive decay produced is commonly digitized and stored in a computer. This method has the advantages of being very quick, easy to add the results of many experiments, (to let the noise average out to near zero), and easy to perform signal enhancements on the raw data. Also the resolution (ability to distinguish to close together frequencies) is largely a product of how good a digitizer you can make. To give you an example an NMR spectrometer aquiring data in continuous wave mode might take ten minutes to record a very high resolution proton spectrum that consists of just one scan. In fourier transform mode it can do one scan every two seconds (or less)! The same result can therefore be obtained in a fraction of the time, or the signal to noise quality much improved in equal time.

When FT spectrometers first came on the market, they gave a huge boost to science, as they made what was very difficult, routine.

The Fourier transform is used to take a function into its reciprocal space. The reciprocal space is used to describe what component of a function behaves with a certain periodicity. Like, suppose you are at the ocean, where waves are coming in with spacing of 20 meters. There is a function describing the height of the water at each point; this function varies everywhere. Your reciprocal space water height function is simpler, for it would be zero everywhere except one high area at 2π/ twenty meters. Just looking at it, you would say, "Oh, that's one cycle per twenty meters!"

Secondly, the process of Fourier transformation upon a function is nearly self-inverting. That is to say, the formula for taking the fourier transform of a function is the complex conjugate of the formula for taking the inverse fourier transform. This is true, at least, up to a constant factor for any valid Fourier transform; the form used above does not have this property, because the fourier transform and its inverse differ by a factor of 2π. However, one can choose both to be the geometric mean, in which case they are again complex conjugates.

Thirdly, the fourier transform of a product of functions f(x)g(x) = the convolution of their individual fourier transforms F(k)oG(k). Applying the principle from earlier, we can reverse this to Fourier transform of F(k)G(k) = f(x)og(x). This is a very useful identity because the convolution comes up in a wide variety of problems, and can be very difficult to calculate otherwise.

One nifty way to think of the Fourier transform is as a change of basis in function space from dirac delta functions to complex corkscrews.

The only nontrivial function which is preserved under Fourier transform is the Gaussian curve.

If the function is periodic, then all components that are not multiples of this wavenumber are 0 - it is a series of spikes. This series is called a Fourier series. If you know in advance that the function is periodic and you know the period, you can save effort by only computing the elements of this series.