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 @

ccrma