They say deep down, everything’s simple – and Mr. Joseph Fourier would probably have agreed. The Discrete Fourier Transform is mathematical operation that takes a complex wave and decomposes it into a combination of many simple sine and cosine waves. These simple waves, when added back up, form something very close to the original wave. In fact, if enough simple waves are used, any complex wave may be nearly perfectly decomposed and recreated using a Fourier transform.
The Fourier transform has many applications in science and engineering. In one application, natural language recognition, DFTs are performed on human speech; different vowels and consonants can be picked out by determining, given a complex wave, which of these simpler sub-waves contribute more to the total and which contribute less (these together determine the “flavor” of the wave). The ever-mentioned “spectrum” is nothing more than a DFT applied to sound; on the x-axis is graphed which simple wave we’re talking about (in terms of frequency) and on the y-axis is graphed how much of that simple wave there is in the complex wave (in terms of amplitude). Spectrums are an interesting way to “peek inside” a complex pattern and see what it’s really made of.
What would a Brother Diamond do? In pursuit of hidden cyclical patterns, I wrote an FFT (Fast Fourier Transform, more on this later) algorithm and applied it to stock data. Here’s Microsoft (MSFT)’s price over the past year…
And here’s its spectrum.
This “spectrum” is another way of representing that price data, and provides an interesting back-door look. Think it contains hidden secrets? Here are some more spectra:
Did I discover something? I don’t think so – at least not yet. No individual frequencies, or bands of frequency, seem to emerge above the others; this suggests that there is nothing systematically cyclic about the stocks’ movements. The downward-cascading pattern of amplitudes is still hard for me to explain – I propose that the Transform best approximates the chart by first “using up” the slower frequencies to clear out the macro movements, and then using smaller amounts of the faster frequencies to “fine-tune”.
How does a DFT work? We seek to find the contribution (amplitude) of one particular component wave to the total. We need a filtration method. There’s a trick we can exploit: the product of two periodic functions of different frequencies has an integral of zero over [0, 2π], while the product of two periodic functions of the same frequency has a positive integral over [0, 2π] (positives are multiplied by positives, negatives by negatives, etc.). This becomes very convenient. If we multiply our complex wave by a simple wave and take the integral of the product – which (a) because multiplication is distributive and the integral of a sum is the same as the sum of integrals is equivalent to the value we’d get by multiplying every single component simple wave by the special simple wave, integrating each separately, and adding them up – and because (b) we know that every component wave other than our desired wave now automatically has an area of zero, while the special wave, multiplied by itself, has a positive area – we know that the (c) entirety of the area of the final integrated product represents nothing more than the area contributed by the single desired wave. Given this “isolated” integral, we can easily go back find the amplitude of our desired wave. Repeat the process for each component frequency and you have a DFT.
A DFT is an O(N²) operation – calculating each simple wave’s coefficient requires N multiplications and additions (during integration), and the process must be repeated for all N coefficients. The FFT (Fast Fourier Transform) refers to a series of algorithms designed to quickly compute the Discrete Fourier Transform – the FFT runs in O(N log(N)) time, much faster especially for large inputs. Sine and cosine waves are periodic; by consequence, many of the DFT’s required calculations are repeated many times. The FFT cleverly breaks down the DFT calculation into alternating periods of repeated calculation, and again, and again, until only unique calculations are performed, and values are re-used. Common recursive algorithms like quicksort and mergesort break inputs into halves, left and right – the FFT, meanwhile breaks its input into even and odd.
Finally: it turns out that if we take a function space (like a vector space, except each point represents a continuous function) – and represent an observed complex wave as a single vector in this function space – and if we project this vector onto each of the “axes” formed by our simple waves – then, the length of each of these projections will be the same as the Fourier coefficients seen in the spectrum. The Fourier transform can be expressed in terms of distance and space.
Well – that’s as deep as I’m going today. Hope you enjoyed and feel free to contact with comments.