# Transformed

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.

1. Richard says:

It’s interesting to read about Fourier transformations, as I have not read about them before. It’s always fun and pleasing to discover isomorphisms between different types of representations — in this case, a complicated vector space on the one hand and representations of the frequencies and amplitudes of the Fourier transform off the original wave on the other. It has been a while since I spent serious time with trigonometry and vectors (nearly five years in fact) but I’m sure there’s plenty of interesting stuff to think about when the details are filtered through.

2. Ben says:

I’ve hedged a bit. I said that “if enough simple waves are used, any complex wave may be nearly perfectly decomposed and recreated using a Fourier transform.” My choice of the words “nearly perfectly” was judicious.

In regards to the discrete Fourier transform, the vector space of real-valued functions on a finite set is finite-dimensional. In this finite-dimensional vector space, the phasors (simple trigonometric waves) comprise an orthonormal basis, and the determination of a function’s Fourier coefficients amounts to nothing more than projection. Of course, each such function has a unique representation as a sum of basis elements, and the question of “convergence” is trivial.

In the infinite-dimensional case, the question of convergence of the Fourier series is much more delicate. Here, of course, we must be precise about exactly which functions we’re considering, on which space, under which conditions, etc… Furthermore, which type of convergence? There are at least three. (See here for some information.)

Speaking very roughly, in an infinite-dimensional inner product space (that is, a Hilbert space) every element “is” an infinite combination of basis elements. Taking infinite sums doesn’t make sense, though. This is hard to convey clearly. Really, there is no mathematical meaning we can give prima facie to the value of an infinite sum — it keeps changing! (What is the sum of 1 – 1 + 1 – 1 + 1 …?) The way that we make sense of things in a Hilbert space is by introducing a norm — a way of measuring the distances between objects — and declaring that an infinite sequence of elements sums to a certain element just when the nth partial sum of this sequence (i.e., a_1 + … + a_n) gets arbitrarily close to this element as n grows large. This allows us to define certain infinite sums indirectly.