Fast wavelet transform

<h2 id="forward-dwt">Forward DWT</h2>
For the <a href="/facts/Discrete_wavelet_transform/19DVnk4n">discrete wavelet transform</a> (DWT), 
one computes <a href="/facts/Recursion/CxSKxJoW">recursively</a>, starting with the coefficient sequence 
 
 
 
 
 s
 
 (
 J
 )
 
 
 
 
 {\displaystyle s^{(J)}}
 
 and counting down from k = J − 1 to some M < J,

s
          
            n
          
          
            (
            k
            )
          
        
        :=
        
          
            1
            2
          
        
        
          ∑
          
            m
            =
            −
            N
          
          
            N
          
        
        
          a
          
            m
          
        
        
          s
          
            2
            n
            +
            m
          
          
            (
            k
            +
            1
            )
          
        
      
    
    {\displaystyle s_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}a_{m}s_{2n+m}^{(k+1)}}
  
 or 
  
    
      
        
          s
          
            (
            k
            )
          
        
        (
        z
        )
        :=
        (
        ↓
        2
        )
        (
        
          a
          
            ∗
          
        
        (
        z
        )
        ⋅
        
          s
          
            (
            k
            +
            1
            )
          
        
        (
        z
        )
        )
      
    
    {\displaystyle s^{(k)}(z):=(\downarrow 2)(a^{*}(z)\cdot s^{(k+1)}(z))}

and

d
 
 n
 
 
 (
 k
 )
 
 
 :=
 
 
 1
 2
 
 
 
 ∑
 
 m
 =
 −
 N
 
 
 N
 
 
 
 b
 
 m
 
 
 
 s
 
 2
 n
 +
 m
 
 
 (
 k
 +
 1
 )
 
 
 
 
 {\displaystyle d_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}b_{m}s_{2n+m}^{(k+1)}}
 
 or 
 
 
 
 
 d
 
 (
 k
 )
 
 
 (
 z
 )
 :=
 (
 ↓
 2
 )
 (
 
 b
 
 ∗
 
 
 (
 z
 )
 ⋅
 
 s
 
 (
 k
 +
 1
 )
 
 
 (
 z
 )
 )
 
 
 {\displaystyle d^{(k)}(z):=(\downarrow 2)(b^{*}(z)\cdot s^{(k+1)}(z))}
 
,
for k = J − 1, J − 2, ..., M and all 
 
 
 
 n
 ∈
 
 Z
 
 
 
 {\displaystyle n\in \mathbb {Z} }
 
. In the Z-transform notation:

<ul><li>The <a href="/facts/Downsampling/gN5Wwrhv">downsampling operator</a> 
 
 
 
 (
 ↓
 2
 )
 
 
 {\displaystyle (\downarrow 2)}
 
 reduces an infinite sequence, given by its <a href="/facts/Z-transform/ERNvDJqt">Z-transform</a>, which is simply a <a href="/facts/Laurent_series/sSMevFU8">Laurent series</a>, to the sequence of the coefficients with even indices, 
 
 
 
 (
 ↓
 2
 )
 (
 c
 (
 z
 )
 )
 =
 
 ∑
 
 k
 ∈
 
 Z
 
 
 
 
 c
 
 2
 k
 
 
 
 z
 
 −
 k
 
 
 
 
 {\displaystyle (\downarrow 2)(c(z))=\sum _{k\in \mathbb {Z} }c_{2k}z^{-k}}
 
.</li>
<li>The starred Laurent-polynomial 
 
 
 
 
 a
 
 ∗
 
 
 (
 z
 )
 
 
 {\displaystyle a^{*}(z)}
 
 denotes the <a href="/facts/Adjoint_filter/GD3wyewB">adjoint filter</a>, it has time-reversed adjoint coefficients, 
 
 
 
 
 a
 
 ∗
 
 
 (
 z
 )
 =
 
 ∑
 
 n
 =
 −
 N
 
 
 N
 
 
 
 a
 
 −
 n
 
 
 ∗
 
 
 
 z
 
 −
 n
 
 
 
 
 {\displaystyle a^{*}(z)=\sum _{n=-N}^{N}a_{-n}^{*}z^{-n}}
 
. (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).</li>
<li>Multiplication is polynomial multiplication, which is equivalent to the convolution of the coefficient sequences.</li></ul>
It follows that

P
          
            k
          
        
        [
        f
        ]
        (
        x
        )
        :=
        
          ∑
          
            n
            ∈
            
              Z
            
          
        
        
          s
          
            n
          
          
            (
            k
            )
          
        
        
        φ
        (
        
          2
          
            k
          
        
        x
        −
        n
        )
      
    
    {\displaystyle P_{k}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(k)}\,\varphi (2^{k}x-n)}

is the orthogonal projection of the original signal f or at least of the first approximation 
 
 
 
 
 P
 
 J
 
 
 [
 f
 ]
 (
 x
 )
 
 
 {\displaystyle P_{J}[f](x)}
 
 onto the <a href="/facts/Linear_subspace/2wtKTgHL">subspace</a> 
 
 
 
 
 V
 
 k
 
 
 
 
 {\displaystyle V_{k}}
 
, that is, with sampling rate of 2k per unit interval. The difference to the first approximation is given by

P
          
            J
          
        
        [
        f
        ]
        (
        x
        )
        =
        
          P
          
            k
          
        
        [
        f
        ]
        (
        x
        )
        +
        
          D
          
            k
          
        
        [
        f
        ]
        (
        x
        )
        +
        ⋯
        +
        
          D
          
            J
            −
            1
          
        
        [
        f
        ]
        (
        x
        )
        ,
      
    
    {\displaystyle P_{J}[f](x)=P_{k}[f](x)+D_{k}[f](x)+\dots +D_{J-1}[f](x),}

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

D
          
            k
          
        
        [
        f
        ]
        (
        x
        )
        :=
        
          ∑
          
            n
            ∈
            
              Z
            
          
        
        
          d
          
            n
          
          
            (
            k
            )
          
        
        
        ψ
        (
        
          2
          
            k
          
        
        x
        −
        n
        )
        ,
      
    
    {\displaystyle D_{k}[f](x):=\sum _{n\in \mathbb {Z} }d_{n}^{(k)}\,\psi (2^{k}x-n),}

with 
 
 
 
 ψ
 
 
 {\displaystyle \psi }
 
 denoting the mother wavelet of the wavelet transform.

<h2 id="inverse-dwt">Inverse DWT</h2>
Given the coefficient sequence 
 
 
 
 
 s
 
 (
 M
 )
 
 
 
 
 {\displaystyle s^{(M)}}
 
 for some M < J and all the difference sequences 
 
 
 
 
 d
 
 (
 k
 )
 
 
 
 
 {\displaystyle d^{(k)}}
 
, k = M,...,J − 1, one computes recursively

s
          
            n
          
          
            (
            k
            +
            1
            )
          
        
        :=
        
          ∑
          
            k
            =
            −
            N
          
          
            N
          
        
        
          a
          
            k
          
        
        
          s
          
            2
            n
            −
            k
          
          
            (
            k
            )
          
        
        +
        
          ∑
          
            k
            =
            −
            N
          
          
            N
          
        
        
          b
          
            k
          
        
        
          d
          
            2
            n
            −
            k
          
          
            (
            k
            )
          
        
      
    
    {\displaystyle s_{n}^{(k+1)}:=\sum _{k=-N}^{N}a_{k}s_{2n-k}^{(k)}+\sum _{k=-N}^{N}b_{k}d_{2n-k}^{(k)}}
  
 or 
  
    
      
        
          s
          
            (
            k
            +
            1
            )
          
        
        (
        z
        )
        =
        a
        (
        z
        )
        ⋅
        (
        ↑
        2
        )
        (
        
          s
          
            (
            k
            )
          
        
        (
        z
        )
        )
        +
        b
        (
        z
        )
        ⋅
        (
        ↑
        2
        )
        (
        
          d
          
            (
            k
            )
          
        
        (
        z
        )
        )
      
    
    {\displaystyle s^{(k+1)}(z)=a(z)\cdot (\uparrow 2)(s^{(k)}(z))+b(z)\cdot (\uparrow 2)(d^{(k)}(z))}

for k = J − 1,J − 2,...,M and all 
 
 
 
 n
 ∈
 
 Z
 
 
 
 {\displaystyle n\in \mathbb {Z} }
 
. In the Z-transform notation:

<ul><li>The <a href="/facts/Upsampling/ndAk3IxG">upsampling operator</a> 
 
 
 
 (
 ↑
 2
 )
 
 
 {\displaystyle (\uparrow 2)}
 
 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 
 
 
 
 (
 ↑
 2
 )
 (
 c
 (
 z
 )
 )
 :=
 
 ∑
 
 n
 ∈
 
 Z
 
 
 
 
 c
 
 n
 
 
 
 z
 
 −
 2
 n
 
 
 
 
 {\displaystyle (\uparrow 2)(c(z)):=\sum _{n\in \mathbb {Z} }c_{n}z^{-2n}}
 
. This linear operator is, in the <a href="/facts/Hilbert_space/aDFMh4lV">Hilbert space</a> 
 
 
 
 
 ℓ
 
 2
 
 
 (
 
 Z
 
 ,
 
 R
 
 )
 
 
 {\displaystyle \ell ^{2}(\mathbb {Z} ,\mathbb {R} )}
 
, the adjoint to the downsampling operator 
 
 
 
 (
 ↓
 2
 )
 
 
 {\displaystyle (\downarrow 2)}
 
.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Lifting_scheme/htMkzoAQ">Lifting scheme</a></li>
<li><a href="/facts/Fast_Fourier_transform/caT7UUCh">Fast Fourier transform</a></li></ul>

<ul><li>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.</li>
<li>I. Daubechies, Ten Lectures on Wavelets. SIAM, 1992.</li>
<li>A.N. Akansu Multiplierless Suboptimal PR-QMF Design Proc. SPIE 1818, Visual Communications and Image Processing, p. 723, November, 1992</li>
<li>A.N. Akansu Multiplierless 2-band Perfect Reconstruction Quadrature Mirror Filter (PR-QMF) Banks US Patent 5,420,891, 1995</li>
<li>A.N. Akansu Multiplierless PR Quadrature Mirror Filters for Subband Image Coding IEEE Trans. Image Processing, p. 1359, September 1996</li>
<li>M.J. Mohlenkamp, <a href="/facts/Cristina_Pereyra/d8YuruQW">M.C. Pereyra</a> Wavelets, Their Friends, and What They Can Do for You (2008 EMS) p. 38</li>
<li><a href="/facts/Barbara_Burke_Hubbard/nRlMrDGS">B.B. Hubbard</a> The World According to Wavelets: The Story of a Mathematical Technique in the Making (1998 Peters) p. 184</li>
<li>S.G. Mallat A Wavelet Tour of Signal Processing (1999 Academic Press) p. 255</li>
<li>A. Teolis Computational Signal Processing with Wavelets (1998 Birkhäuser) p. 116</li>
<li>Y. Nievergelt Wavelets Made Easy (1999 Springer) p. 95</li></ul>
<h2 id="further-reading">Further reading</h2>
<a href="/facts/Gregory_Beylkin/BDCD6FVE">G. Beylkin</a>, <a href="/facts/Ronald_Coifman/vFyXxtpx">R. Coifman</a>, <a href="/facts/Vladimir_Rokhlin_Jr./tgMX1qvy">V. Rokhlin</a>, "Fast wavelet transforms and numerical algorithms" Comm. Pure Appl. Math., 44 (1991) pp. 141–183 <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fcpa.3160440202">10.1002/cpa.3160440202</a> (This article has been cited over 2400 times.)

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"Fast Wavelet Transform (FWT) Algorithm". MathWorks. Retrieved 2018-02-20. <a href="https://www.mathworks.com/help/wavelet/ug/fast-wavelet-transform-fwt-algorithm.html?requestedDomain=true" target="_blank">https://www.mathworks.com/help/wavelet/ug/fast-wavelet-transform-fwt-algorithm.html?requestedDomain=true</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
</ol>

Fast wavelet transform open-in-new

Fast wavelet transform