Fast wavelet transform

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" onto the space formula_1; in theory by computing the scalar products 
where formula_3 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 or at least some good approximation of the original signal in formula_1. 
The MRA is characterised by its scaling sequence
and its wavelet sequence 
(some coefficients might be zero). Those allow to compute the wavelet coefficients formula_10, at least some range "k=M...,J-1", without having to approximate the integrals in the corresponding scalar products. Instead, one can directly, with the help of convolution and decimation operators, compute those coefficients from the first approximation formula_11.
Forward DWT.
For the discrete wavelet transform (DWT), 
one computes recursively, starting with the coefficient sequence formula_11 and counting down from "k=J-1" to some "M<J",
and 
for "k=J-1,J-2...,M" and all formula_17. In the Z-transform notation:
It follows that
is the orthogonal projection of the original signal "f" or at least of the first approximation formula_23 onto the subspace formula_24, 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
with formula_27 denoting the "mother wavelet" of the wavelet transform.
Inverse DWT.
Given the coefficient sequence formula_28 for some "M<J" and all the difference sequences formula_29, "k=M...,J-1", one computes recursively
for "k=J-1,J-2...,M" and all formula_17. In the Z-transform notation:
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.)