The fast wavelet transform is a mathematical algorithm designed to turn a waveform or signal in the time domain into a sequence of coefficients based on an orthogonal basis of small finite waves, or wavelets. The transform can be easily extended to multidimensional signals, such as images, where the time domain is replaced with the space domain. This algorithm was introduced in 1989 by Stéphane Mallat.

It has as theoretical foundation the device of a finitely generated, orthogonal multiresolution analysis (MRA). In the terms given there, one selects a sampling scale J with sampling rate of 2J per unit interval, and projects the given signal f; in theory by computing the scalar productss

is the scaling function of the chosen wavelet transform; in practice by any suitable sampling procedure under the condition that the signal is highly oversampled, so

is the orthogonal projection.

The MRA is characterised by its scaling sequence

1. or, as Z-transform

and its wavelet sequence

, at least some range k=M,...,J-1.

Forward DWT

For the discrete wavelet transform (DWT), one computes recursively and counting down from k = J 1 to some M < J,

and

1. ,

for k = J 1, J 2, ..., M. In the Z-transform notation:

• The downsampling operator reduces an infinite sequence, given by its Z-transform, which is simply a Laurent series.

• denotes the adjoint filter, it has time-reversed. (The adjoint of a real number being the number itself, of a complex number its conjugate, of a real matrix the transposed matrix, of a complex matrix its hermitian adjoint).

• Multiplication is polynomial multiplication, which is equivalent to the convolution of the coefficient sequences.

It follows that

is the orthogonal projection of the original signal f onto the subspace, that is, with sampling rate of 2k per unit interval. The difference to the first approximation is given by

where the difference or detail signals are computed from the detail coefficients as

denoting the mother wavelet of the wavelet transform.

Inverse DWT

for some M<J, k=M,...,J−1, one computes recursively

for k = J−1,J−2,...,M. In the Z-transform notation:

• The upsampling operator. This linear operator is, in the Hilbert space.

See also

• Lifting scheme

• Fast Fourier transform

• Fast Walsh–Hadamard transform

References

• S.G. Mallat "A Theory for Multiresolution Signal Decomposition: The Wavelet Representation" IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 2, no. 7. July 1989.

• I. Daubechies, Ten Lectures on Wavelets. SIAM, 1992.

• A.N. Akansu Multiplierless Suboptimal PR-QMF Design Proc. SPIE 1818, Visual Communications and Image Processing, p. 723, November, 1992

• A.N. Akansu Multiplierless 2-band Perfect Reconstruction Quadrature Mirror Filter (PR-QMF) Banks US Patent 5,420,891, 1995

• A.N. Akansu Multiplierless PR Quadrature Mirror Filters for Subband Image Coding IEEE Trans. Image Processing, p. 1359, September 1996

• M.J. Mohlenkamp, M.C. Pereyra Wavelets, Their Friends, and What They Can Do for You (2008 EMS) p. 38

• B.B. Hubbard The World According to Wavelets: The Story of a Mathematical Technique in the Making (1998 Peters) p. 184

• S.G. Mallat A Wavelet Tour of Signal Processing (1999 Academic Press) p. 255

• A. Teolis Computational Signal Processing with Wavelets (1998 Birkhäuser) p. 116

• Y. Nievergelt Wavelets Made Easy (1999 Springer) p. 95

Further reading

G. Beylkin, R. Coifman, V. Rokhlin, "Fast wavelet transforms and numerical algorithms" Comm. Pure Appl. Math., 44 (1991) pp. 141–183 (This article has been cited over 2400 times.)