Fourier Analysis

If we physically analyze a sound, we could create a set of oscillators, each tuned to a slightly different frequency, and let the sound swing them. Whatever frequencies were contained in the sound would excite the corresponding oscillators. This is essentially what happens in our ear. 

Alternatively, instead of building a set of oscillators, we could analyze the sound wave mathematically, to find out which oscillators would be excited. Each oscillator corresponds to a sinusoidal weight function of specific frequency. If the sound is digitized, we would multiply its samples by the corresponding weights and add them all up (without digitizing we would have to multiply the sound wave by the sine function and then integrate it). The resulting number tells us how much of a given frequency there is in this particular sound wave. A set of such numbers, corresponding to various frequencies, is called a Fourier transform (more precisely, a Digital Fourier Transform, DFT) or a frequency spectrum of the sound. 

What does the Fourier transform have to do with the wavelet transformation? Look at the weights we use in our analysis. These are nothing else but some very particular basis vectors. They just happen to follow the shape of a sine function (compare it with the Haar basis).


Notice that it's not enough to use the sine-shaped functions. For completeness, we have to add the cosine-shaped functions as well. Even though they correspond to the same frequencies as the sine-shaped ones, they describe the out-of-phase swings of the oscillators. As you can see, the Fourier basis can be obtained by sampling sine and cosine waves. 

Fourier Synthesis

It so happens that the Fourier wavelets form an orthogonal system -- if you take a scalar product of any two of them, you'll get zero. Also, with proper normalization, you can make the squares of these vectors equal to one. N of these vectors form a perfect orthonormal basis in N-dimensional space. In other words, any buffer with N samples can be projected onto these N vectors giving N numbers (which are called Fourier coefficients). These numbers form the digital Fourier transform of the buffer. 
Conversely, given those numbers we can reconstitute the original buffer. It is enough to multiply each basis vector by its corresponding Fourier coefficient and add them all up to obtain one N-dimensional vector exactly equal to the original sample buffer. The process of reconstructing the sound wave from its Fourier coefficients is called Fourier synthesis. Since each basis vector is a sampled sine (cosine) wave of a given frequency, you see that by adding up these waves with appropriate coefficients you can re-create any sound wave. In this sense a sound wave is the sum of the pure frequencies contained in it. 

We now know (theoretically) how to extract these frequencies (Fourier analysis) as well as synthesize arbitrary sounds from them (Fourier synthesis). It's time for some practical algorithms. But before we get to it, we have to learn some complex numbers. 

