0.2 Computational harmonic analysis  (Page 2/3)

Wavelet bases

Wavelet bases, like Fourier bases, reveal the signal regularity through the amplitude of coefficients, and their structure leadsto a fast computational algorithm. However, wavelets are well localized and few coefficients are needed to represent localtransient structures. As opposed to a Fourier basis, a wavelet basis defines a sparse representation of piecewise regularsignals, which may include transients and singularities. In images, large wavelet coefficients are located in the neighborhoodof edges and irregular textures.

The story began in 1910, when Haar (Haar:10) constructed a piecewise constantfunction

the dilations and translations of which generate an orthonormal basis

of the space ${\mathbf{L}}^{\mathbf{2}}\left(\mathbb{R}\right)$ of signals having a finite energy

Let us write $⟨f,g⟩={\int }_{-\infty }^{+\infty }f\left(t\right)g^{*}\left(t\right)dt$ —the inner product in ${\mathbf{L}}^{\mathbf{2}}\left(\mathbb{R}\right)$ .  Any finite energy signal $f$ can thus be represented by its wavelet inner-product coefficients

and recovered by summing them in this wavelet orthonormal basis:

Each Haar wavelet ${\psi }_{j,n}\left(t\right)$ has a zero average over its support $[2^{j}n,2^j(n+1)]$ . If $f$ is locally regular and $2^j$ is small, then it is nearly constant over this interval andthe wavelet coefficient $⟨f,{\psi }_{j,n}⟩$ is nearly zero. This means that large wavelet coefficientsare located at sharp signal transitions only.

With a jump in time, the story continues in 1980, when Strömberg (Stromberg:81) found a piecewise linear function ψ that also generates an orthonormal basis and gives better approximations of smooth functions.Meyer was not aware of this result, and motivated by the work of Morlet and Grossmann over continuouswavelet transform, he tried to prove that there existsno regular wavelet ψ that generates an orthonormal basis. This attempt was a failure since he ended up constructing awhole family of orthonormal wavelet bases, with functions ψ that are infinitely continuously differentiable (Meyer:86). This was the fundamental impulse that led to a widespreadsearch for new orthonormal wavelet bases, which culminated in the celebrated Daubechies waveletsof compact support (Daubechies:88).

The systematic theory for constructing orthonormal wavelet bases was established by Meyer and Mallat throughthe elaboration of multiresolution signal approximations (Mallat:89b), as presented in Chapter 7.It was inspired by original ideas developed in computer vision by Burt and Adelson (BurtA:83)to analyze images at several resolutions. Digging deeper into the properties of orthogonal waveletsand multiresolution approximations brought to lighta surprising link with filter banks constructed with conjugate mirror filters,and a fast wavelet transform algorithm decomposing signals of size N with $O\left(N\right)$ operations (Mallat:89).

Filter banks

Motivated by speech compression, in 1976 Croisier, Esteban, and Galand (CroisierEG:76) introducedan invertible filter bank, which decomposesa discrete signal $f\left[n\right]$ into two signals of half its size using a filtering and subsampling procedure.They showed that $f\left[n\right]$ can be recovered from these subsampled signals by cancelingthe aliasing terms with a particular class of filters called conjugate mirror filters . This breakthrough led to a 10-year research effort to builda complete filter bank theory. Necessary and sufficient conditions for decomposing a signal in subsampledcomponents with a filtering scheme, and recovering the same signal with an inverse transform, were established bySmith and Barnwell (SmithB:84), Vaidyanathan (Vaidyanathan:87), andVetterli (Vetterli:86).