A Brief Course on Wavelets

Wei-Chang Shann ���

Department of Mathematics, National Central University July 16, 1996

• Basic terms and ideas

• Key points

• Some examples of wavelets

• Some examples of applications

Department of Electrical Engineering, NCU

A Few Basic Terms

• A function f (x) is said to be in L^{2}(R) if

∫_{−∞}^{∞} |f (x)|^{2} dx < ∞

and the integration is in the Lebesgue sense. Essentially it says f (x) has finite energy. In practice, all signals, images, functions representing physical phenomena are L^{2}(R) functions.

• L^{2}(R) is an infinite dimensional vector space. We can define the length ∥f∥ and inner products (f, g) on L^{2}(R) analogous to the vectors on the plane R^{2}.

• The Fourier transform of f(x) is

f^{}ˆ (ω) = ∫_{−∞}^{∞} f (x)e^{−iωx} dx.

If x is the time variable, f (x) is said to be on the time domain and f^{}ˆ (ω) on the frequency domain. Theoretically, a function cannot be both time-limited and band-limited. But in practice both |f (x)| and |f^{}ˆ (ω)| tend to zero for large |x| and |ω|.

• The smooth, slow changing part of f (x) corresponds to the low frequency part of the f^{}ˆ (ω); the rough, quick changing part of f (x) corresponds to the high frequency part of the f^{}ˆ (ω). In practice the magnitudes of high frequencies are small, and noises are in high frequencies.

Implementations of Wavelets

• 1910, Haar functions. A compactly supported discontinuous wavelet.

ψ(x) = \{ \begin{matrix}1 & for x ∈ [0, 1/2) \\ −1 & for x ∈ [1/2, 1) \\ 0 & otherwise. \end{matrix}

Now a special case (p = 1) in the Daubechies family of wavelets.

• 1985, Meyer found the first set of modern wavelets. They are band-limited but decay slowly in time.

• Mallat and Meyer found a recipe to build wavelets from a multiresolusion analysis.

• 1986, Battle and Lemarié independently constructed wavelets from B-splines. These ones have exponential decay.

• 1988, Daubechies published a family of wavelets with compact supports. So the filters have finite lengths, or, they are Finite Impulse Response (FIR) filters. Their periodic variations are easily constructed.

• 1992, biorthogonal wavelets by Chui, Daubechies et al., wavelet packets by Coifman, Wickerhauser et al.

• 1993, wavelets on finite intervals by Daubechies, Meyer, Jawerth et al. Then there come wavelets on the sphere.

Other Implementations

• 1991, coiflet made by Daubechies (responded to a request by Coifman) for efficiency of numerical quadratures.

• 1992, anti-derivatives of wavelets used in the framework of Galerkin mathod for solving differential equations, by Dahmen et al., Jaffard, Jawerth et al., and Xu/Shann.

• 1993, Donoho’s wavelets for statistical estimations, (late) Harten’s wavelets for numerical computations.

• 1994, difference wavelets by Chern/Shann et al.

• 1995, the lifting scheme for the construction of biorthogonal wavelets, by Sweldens et al.

Software Packages about Wavelets

Software packages are available to experiment with wavelets, or to design your own wavelets.

• Liftpack, based on lifting scheme, design your own biorthogonal

wavelets.

http://www.cs.sc.edu:80/˜ fernande/liftpack/index.html

• GenLOT by Nguyen’s Multirate Signal Processing Group, design your own filters; also described in the book “Wavelets and Filter Banks” by Strang and Nguyen.

http://saigon.ece.wisc.edu/ waveweb/QMF.html

• The WavBox ToolSmith by Taswell, adaptive wavelet packet decompositions with New Satisficing Search Algorithms, written in Matlab M-files.

http://www.wavbox.com

• The Wavelet Toolbox for Matlab.

http://www.mathworks.com/wavelet.html

• S^{+}Wavelets: An S-Plus module.

http://www.mathsoft.com/splsprod/wavelets.html

A Few Key Points

Let us focus on the Daubechies wavelets of order p, p ≥ 1.

• The fast algorithm for discrete Fourier transform (FFT) has a complexity O(N log N). The fast algorithm for discrete wavelet transform (FWT) has a complexity O(N), actually about 8pN flops. The reconstruction matrices of the above transforms are basically the transpose of the decomposition matrices.

• ψ(x) is perpendicular to all polynomials of degree ≤ p−1. So the low resolution space V_{0} is rich enough to contain all polynomials of degree ≤ p − 1.

• If f (x) is m-times continuously differentiable for x near the point

\frac{k}{2^{j}}, then

|(f (x), ψ_{jk}(x))| = O(2^{−(j+\frac{1}{2})M} )

where M = min{m, p − 1}.

• All functions satisfy the Heisenberg uncertainty principle:

Area of Heisenberg box on time-frequency phase plane ≥ \frac{1}{π}.

Windowed Fourier transforms use fixed Heisenberg boxes around the phase plane. Wavelet transforms use those boxes automatically change their shapes for efficiency.

Typical Applications

• Approximation. Wavelets have good approximation ability because the low resolution space V_{0} is rich.

• Because of the approximation ability, wavelets can be applied to solve differential equations. The wavelets derived methods are particularly efficient for phenomena mixed with large and small scales of changing.

• Signal and image processing: compression, edge detectiong, pattern and texture recognization (recognition), denoising (wavelet shrinkage).

• Fast algorithms for matrix-vector multiplications; can be applied to solve certain types of integral equations.

Denosing by Wavelets Shrinkage

The basic idea is to take the wavelet transform of a signal, shrink it and then take the inverse transform.

If we simply shrink the signal in wavelet domain by 0.03, and take the inverse transform, we get roughly denoised. There are statistical technics to do the shrinkage (Donoho).

The Time-Frequency Phase Plane

• The impulse function (time sampling): sharp in time, vague in frequency.

• The sinusoid (Fourier transform): sharp in frequency, vague in time.

• The windowed cosine (windowed Fourier/cosine transform): local in both time and frequency, but fixed window dimensions at all positions, no adaptivity for efficiency.

• The wavelets: Variable window dimensions adapted to the position at the phase plane.