Fast wavelet transform

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Fast wavelet transform" – news · newspapers · books · scholar · JSTOR (January 2010) (Learn how and when to remove this message) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2018) (Learn how and when to remove this message) (Learn how and when to remove this message)

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.^[1]

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 2^J per unit interval, and projects the given signal f onto the space ${\displaystyle V_{J}}$; in theory by computing the scalar products

${\displaystyle s_{n}^{(J)}:=2^{J}\langle f(t),\varphi (2^{J}t-n)\rangle ,}$

where ${\displaystyle \varphi }$ 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

${\displaystyle P_{J}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(J)}\,\varphi (2^{J}x-n)}$

is the orthogonal projection or at least some good approximation of the original signal in ${\displaystyle V_{J}}$.

The MRA is characterised by its scaling sequence

${\displaystyle a=(a_{-N},\dots ,a_{0},\dots ,a_{N})}$ or, as Z-transform, ${\displaystyle a(z)=\sum _{n=-N}^{N}a_{n}z^{-n}}$

and its wavelet sequence

${\displaystyle b=(b_{-N},\dots ,b_{0},\dots ,b_{N})}$ or ${\displaystyle b(z)=\sum _{n=-N}^{N}b_{n}z^{-n}}$

(some coefficients might be zero). Those allow to compute the wavelet coefficients ${\displaystyle d_{n}^{(k)}}$, 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 ${\displaystyle s^{(J)}}$.