Fourier Analysis Explained

What I learned in Music 320

Very rarely (at Stanford, at least) do you see an explanation of Fourier Transforms which makes sense!

The Fourier Transform

In a nutshell, this is it: the Fourier Transform is a projection of any function onto complex exponentials of the form exp(jwx), where w is the frequency. Mathematically, the integral of the product of two functions is an inner product and the complex exponentials are a convenient set of orthogonal basis functions for an arbitrary function space. That's Fourier's theorem.

A Simple Digital Explanation

Interpreted another way, we can view a sampled signal (i.e. a list of numbers) as a vector of arbitrary dimension. We can define a vector space containing all such possible sampled signals. Now, what are some reasonable basis vectors which span this space? One convenient basis is the "natural" basis, which contains the orthogonal unit vectors 1,0,0,0... 0,1,0,0,... ...,0,0,1. But a projection onto these basis vectors yields little insight. A more useful basis is the normalized exponentials, exp(jwx). A projection onto this basis allows us to reconstruct the signal as a sum of exponentials! Why is this good? Complex exponentials are sinusoids. We hear sinusoids - or, at least, we can detect the presence or absence of sinusoids at various frequencies. Thus, such a transform is musically relevant. There are lots of other good reasons why we might like such a transform. Most significantly, the operation of filtering is very simple once we are in the frequency domain - in order to change the amount of a certain frequency which is in a signal, we just multiply that coefficient by a constant.

The DFT revealed

The transform I've described is very close to the Discrete Fourier Transform. It's not exactly the same, unfortunately, because the DFT is not normalized. That is, instead of projecting onto exp(jwx), we're actually projecting onto 1/N * exp(jwx), where N is the number of samples. Oh well - blame the people who invented the DFT. The point, however, remains: the DFT is a convenient way of breaking down a signal into its frequency components. Best of all, efficient algorithms (called Fast Fourier Transforms) exist to compute the DFT, which allow us to perform efficient filtering by taking the DFT, multiplying the frequency coefficients, and then reconstructing the signal (i.e. taking the inverse DFT.) Doing this in the time domain requires linear convolution, which is in general much more time-intensive.

lantz @