Cascade algorithm

<h2 id="successive-approximation">Successive approximation</h2>
The iterative algorithm generates successive approximations to ψ(t) or φ(t) from {h} and {g} filter coefficients. If the algorithm converges to a fixed point, then that fixed point is the basic scaling function or wavelet.
The iterations are defined by

φ
          
            (
            k
            +
            1
            )
          
        
        (
        t
        )
        =
        
          ∑
          
            n
            =
            0
          
          
            N
            −
            1
          
        
        h
        [
        n
        ]
        
          
            2
          
        
        
          φ
          
            (
            k
            )
          
        
        (
        2
        t
        −
        n
        )
      
    
    {\displaystyle \varphi ^{(k+1)}(t)=\sum _{n=0}^{N-1}h[n]{\sqrt {2}}\varphi ^{(k)}(2t-n)}

For the kth iteration, where an initial φ(0)(t) must be given.
The frequency domain estimates of the basic scaling function is given by

Φ
          
            (
            k
            +
            1
            )
          
        
        (
        ω
        )
        =
        
          
            1
            
              2
            
          
        
        H
        
          (
          
            
              ω
              2
            
          
          )
        
        
          Φ
          
            (
            k
            )
          
        
        
          (
          
            
              ω
              2
            
          
          )
        
      
    
    {\displaystyle \Phi ^{(k+1)}(\omega )={\frac {1}{\sqrt {2}}}H\left({\frac {\omega }{2}}\right)\Phi ^{(k)}\left({\frac {\omega }{2}}\right)}

and the limit can be viewed as an infinite product in the form

Φ
          
            (
            ∞
            )
          
        
        (
        ω
        )
        =
        
          ∏
          
            k
            =
            1
          
          
            ∞
          
        
        
          
            1
            
              2
            
          
        
        H
        
          (
          
            
              ω
              
                2
                
                  k
                
              
            
          
          )
        
        
          Φ
          
            (
            ∞
            )
          
        
        (
        0
        )
        .
      
    
    {\displaystyle \Phi ^{(\infty )}(\omega )=\prod _{k=1}^{\infty }{\frac {1}{\sqrt {2}}}H\left({\frac {\omega }{2^{k}}}\right)\Phi ^{(\infty )}(0).}

If such a limit exists, the spectrum of the scaling function is

Φ
        (
        ω
        )
        =
        
          ∏
          
            k
            =
            1
          
          
            ∞
          
        
        
          
            1
            
              2
            
          
        
        H
        
          (
          
            
              ω
              
                2
                
                  k
                
              
            
          
          )
        
        
          Φ
          
            (
            ∞
            )
          
        
        (
        0
        )
      
    
    {\displaystyle \Phi (\omega )=\prod _{k=1}^{\infty }{\frac {1}{\sqrt {2}}}H\left({\frac {\omega }{2^{k}}}\right)\Phi ^{(\infty )}(0)}

The limit does not depends on the initial shape assume for φ(0)(t). This algorithm converges reliably to φ(t), even if it is discontinuous.
From this scaling function, the wavelet can be generated from

ψ
        (
        t
        )
        =
        
          ∑
          
            n
            =
            −
            ∞
          
          
            ∞
          
        
        g
        [
        n
        ]
        
          
            2
          
        
        
          φ
          
            (
            k
            )
          
        
        (
        2
        t
        −
        n
        )
        .
      
    
    {\displaystyle \psi (t)=\sum _{n=-\infty }^{\infty }g[n]{\sqrt {2}}\varphi ^{(k)}(2t-n).}

Successive approximation can also be derived in the frequency domain.

<ul><li><a href="/facts/C._Sidney_Burrus/E4tsUg4S">C.S. Burrus</a>, R.A. Gopinath, H. Guo, Introduction to Wavelets and Wavelet Transforms: A Primer, Prentice-Hall, 1988, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-13-489600-9.</li>
<li><a href="http://cnx.org/content/m10486/latest/">http://cnx.org/content/m10486/latest/</a></li>
<li><a href="http://plan9.bell-labs.co/who/wim/cascade/">http://plan9.bell-labs.co/who/wim/cascade/</a> <a href="https://web.archive.org/web/20070615055323/http://cm.bell-labs.com/cm/ms/who/wim/cascade/index.html">Archived</a> 2007-06-15 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a></li></ul>

Cascade algorithm open-in-new

Cascade algorithm