Editing Fast wavelet transform (section)

{{Short description|Mathematical algorithm}}
{{Multiple issues|
{{Refimprove|date=January 2010}}
{{More footnotes|date=February 2018}}
}}
The '''fast wavelet transform''' is a [[mathematics|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]].<ref>{{cite web |title=Fast Wavelet Transform (FWT) Algorithm |url=https://www.mathworks.com/help/wavelet/ug/fast-wavelet-transform-fwt-algorithm.html?requestedDomain=true |publisher=[[MathWorks]] |access-date=2018-02-20}}</ref>

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<sup>''J''</sup> per unit interval, and projects the given signal ''f'' onto the space <math>V_J</math>; in theory by computing the [[dot product|scalar product]]s 

:<math>s^{(J)}_n:=2^J \langle f(t),\varphi(2^J t-n) \rangle,</math> 

where <math>\varphi</math> is the [[Wavelet#Scaling_function|scaling function]] of the chosen wavelet transform; in practice by any suitable sampling procedure under the condition that the signal is highly oversampled, so
:<math> P_J[f](x):=\sum_{n\in\Z} s^{(J)}_n\,\varphi(2^Jx-n)</math>
is the [[orthogonal projection]] or at least some good approximation of the original signal in <math>V_J</math>. 

The MRA is characterised by its scaling sequence

:<math>a=(a_{-N},\dots,a_0,\dots,a_N)</math> or, as [[Z-transform]], <math>a(z)=\sum_{n=-N}^Na_nz^{-n}</math>

and its wavelet sequence 

:<math>b=(b_{-N},\dots,b_0,\dots,b_N)</math> or <math>b(z)=\sum_{n=-N}^Nb_nz^{-n}</math>

(some coefficients might be zero). Those allow to compute the wavelet coefficients <math>d^{(k)}_n</math>, 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 <math>s^{(J)}</math>.