Editing Fast wavelet transform

{{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>.

== Forward DWT ==
For the [[discrete wavelet transform]] (DWT), 
one computes [[recursion|recursively]], starting with the coefficient sequence <math>s^{(J)}</math> and counting down from ''k = J &minus; 1'' to some ''M < J'',

[[Image:Wavelets_-_DWT.png|thumb|390px|single application of a wavelet filter bank, with filters g=a<sup>*</sup>, h=b<sup>*</sup>]]
:<math>
s^{(k)}_n:=\frac12 \sum_{m=-N}^N a_m s^{(k+1)}_{2n+m}
</math> or <math>
s^{(k)}(z):=(\downarrow 2)(a^*(z)\cdot s^{(k+1)}(z))
</math>
and 
:<math>
d^{(k)}_n:=\frac12 \sum_{m=-N}^N b_m s^{(k+1)}_{2n+m}
</math> or <math>
d^{(k)}(z):=(\downarrow 2)(b^*(z)\cdot s^{(k+1)}(z))
</math>,

for ''k = J &minus; 1, J &minus; 2, ..., M'' and all <math>n\in\Z</math>. In the Z-transform notation:
[[Image:Wavelets_-_Filter_Bank.png|thumb|400px|recursive application of the filter bank]]
:* The [[downsampling|downsampling operator]] <math>(\downarrow 2)</math> reduces an infinite sequence, given by its [[Z-transform]], which is simply a [[Laurent series]], to the sequence of the coefficients with even indices, <math>(\downarrow 2)(c(z))=\sum_{k\in\Z}c_{2k}z^{-k}</math>. 
:* The starred Laurent-polynomial <math>a^*(z)</math> denotes the [[adjoint filter]], it has ''time-reversed'' adjoint coefficients, <math>a^*(z)=\sum_{n=-N}^N a_{-n}^*z^{-n}</math>. (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

:<math>P_k[f](x):=\sum_{n\in\Z} s^{(k)}_n\,\varphi(2^kx-n)</math>

is the orthogonal projection of the original signal ''f'' or at least of the first approximation <math>P_J[f](x)</math> onto the [[linear subspace|subspace]] <math>V_k</math>, that is, with sampling rate of 2<sup>''k''</sup> per unit interval. The difference to the first approximation is given by

:<math>P_J[f](x)=P_k[f](x)+D_k[f](x)+\dots+D_{J-1}[f](x), </math>

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

:<math>D_k[f](x):=\sum_{n\in\Z} d^{(k)}_n\,\psi(2^kx-n), </math>

with <math>\psi</math> denoting the ''mother wavelet'' of the wavelet transform.

==Inverse DWT==
Given the coefficient sequence <math>s^{(M)}</math> for some ''M''&nbsp;<&nbsp;''J'' and all the difference sequences <math>d^{(k)}</math>, ''k''&nbsp;=&nbsp;''M'',...,''J''&nbsp;−&nbsp;1, one computes recursively
:<math>
s^{(k+1)}_n:=\sum_{k=-N}^N a_k s^{(k)}_{2n-k}+\sum_{k=-N}^N b_k d^{(k)}_{2n-k}
</math> or <math>
s^{(k+1)}(z)=a(z)\cdot(\uparrow 2)(s^{(k)}(z))+b(z)\cdot(\uparrow 2)(d^{(k)}(z))
</math>
for ''k'' = ''J''&nbsp;−&nbsp;1,''J''&nbsp;−&nbsp;2,...,''M'' and all <math>n\in\Z</math>. In the Z-transform notation:
:* The [[upsampling|upsampling operator]] <math>(\uparrow 2)</math> creates zero-filled holes inside a given sequence. That is, every second element of the resulting sequence is an element of the given sequence, every other second element is zero or <math>(\uparrow 2)(c(z)):=\sum_{n\in\Z}c_nz^{-2n}</math>. This linear operator is, in the [[Hilbert space]] <math>\ell^2(\Z,\R)</math>, the adjoint to the downsampling operator <math>(\downarrow 2)</math>.

==See also==
* [[Lifting scheme]]
*[[Fast Fourier transform]]

==References==
{{reflist}}
* 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, [[Cristina Pereyra|M.C. Pereyra]] ''Wavelets, Their Friends, and What They Can Do for You'' (2008 EMS) p. 38
* [[Barbara Burke Hubbard|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==
[[Gregory Beylkin|G. Beylkin]], [[Ronald Coifman|R. Coifman]], [[Vladimir Rokhlin Jr.|V. Rokhlin]], "Fast wavelet transforms and numerical algorithms"  ''Comm. Pure Appl. Math.'', 44 (1991) pp. 141–183 {{doi|10.1002/cpa.3160440202}} (This article has been cited over 2400 times.)

[[Category:Wavelets]]
[[Category:Discrete transforms]]