0.2 Computational harmonic analysis

Fourier and wavelet bases are the journey's starting point. They decompose signals over oscillatory waveforms that reveal many signal properties andprovide a path to sparse representations.Discretized signals often have a very large size $N\ge {10}^6$ , and thus can only be processed by fast algorithms,typically implemented with $O(NlogN)$ operations and memories. Fourier and wavelet transforms illustrate the strong connectionbetween well-structured mathematical tools andfast algorithms.

The fourier kingdom

The Fourier transform is everywhere in physics and mathematics because it diagonalizestime-invariant convolution operators. It rules over linear time-invariant signal processing, the building blocks of whichare frequency filtering operators.

Fourier analysis represents any finite energy function $f\left(t\right)$ as a sum of sinusoidal waves ${\mathrm{e}}^{i\omega t}$ :

The amplitude $\widehat{f}\left(\omega \right)$ of each sinusoidal wave ${\mathrm{e}}^{i\omega t}$ is equal to its correlation with $f$ , also called Fourier transform:

The more regular $f\left(t\right)$ , the faster the decay of the sinusoidal wave amplitude $|\widehat{f}\left(\omega \right)|$ when frequency ω increases.

When $f\left(t\right)$ is defined only on an interval, say $[0,1]$ , then the Fourier transformbecomes a decomposition in a Fourier orthonormal basis ${\left\{{\mathrm{e}}^{i2\pi mt}\right\}}_{m\in \mathbb{Z}}$ of ${\mathbf{L}}^{\mathbf{2}}\left(\mathbb{R}\right)[0,1]$ . If $f\left(t\right)$ is uniformly regular, then its Fourier transformcoefficients also have a fast decay when the frequency $2\pi m$ increases, so it can be easily approximated with few low-frequencyFourier coefficients. The Fourier transform therefore defines a sparse representation of uniformly regular functions.

Over discrete signals, the Fourier transform is a decomposition in a discrete orthogonal Fourier basis ${\left\{{\mathrm{e}}^{i2\pi kn/N}\right\}}_{0\le k<N}$ of ${\mathbb{C}}^N$ , which has properties similar to a Fourier transform on functions. Its embedded structure leads to fast Fourier transform (FFT) algorithms, which compute discrete Fouriercoefficients with $O(NlogN)$ instead of N ² . This FFT algorithm is a cornerstone of discrete signal processing.

As long as we are satisfied with linear time-invariant operators or uniformly regular signals, the Fourier transform providessimple answers to most questions. Its richness makes it suitable for a wide range of applications such as signal transmissions orstationary signal processing. However, to represent a transient phenomenon—a word pronounced at a particular time, an applelocated in the left corner of an image—the Fourier transform becomes a cumbersome tool that requires many coefficients torepresent a localized event. Indeed, the support of ${\mathrm{e}}^{i\omega t}$ covers the whole real line, so $\widehat{f}\left(\omega \right)$ depends on the values $f\left(t\right)$ for all times $t\in \mathbb{R}$ . This global “mix” of information makes it difficult to analyze or represent any localproperty of $f\left(t\right)$ from $\widehat{f}\left(\omega \right)$ .