12.12 Computing the scaling function: the cascade algorithm

Given coefficients $\{h(n)\}$ that satisfy the regularity conditions, we can iteratively calculate samples of $\phi (t)$ on a fine grid of points $\{t\}$ using the cascade algorithm . Once we have obtained $\phi (t)$ , the wavelet scaling equation can be used to construct $\psi (t)$ .

In this discussion we assume that $H(z)$ is causal with impulse response length $N$ . Recall, from our discussion of the regularity conditions , that this implies $\phi (t)$ will have compact support on the interval $\left[0 , N-1\right]$ . The cascade algorithm is described below.

1. Consider the scaling function at integer times $t=m\in \{0, \dots , N-1\}$ : $$\phi (m)=\sqrt{2}\sum_{n=0}^{N-1} h(n)\phi (2m-n)$$ Knowing that $\phi (t)=0$ for $t\notin \left[0 , N-1\right]$ , the previous equation can be written using an $N$ x $N$ matrix. In the case where $N=4$ , we have
   $$\begin{pmatrix}\phi (0)\\ \phi (1)\\ \phi (2)\\ \phi (3)\\ \end{pmatrix}=\sqrt{2}\begin{pmatrix}h(0) & 0 & 0 & 0\\ h(2) & h(1) & h(0) & 0\\ 0 & h(3) & h(2) & h(1)\\ 0 & 0 & 0 & h(3)\\ \end{pmatrix}\begin{pmatrix}\phi (0)\\ \phi (1)\\ \phi (2)\\ \phi (3)\\ \end{pmatrix}$$
   $$\text{where}H=\begin{pmatrix}h(0) & 0 & 0 & 0\\ h(2) & h(1) & h(0) & 0\\ 0 & h(3) & h(2) & h(1)\\ 0 & 0 & 0 & h(3)\\ \end{pmatrix}$$ The matrix $H$ is structured as a row-decimated convolution matrix . From the matrix equation above ( [link] ), we see that $\left(\begin{array}{c}\phi (0)\\ \phi (1)\\ \phi (2)\\ \phi (3)\end{array}\right)$ must be (some scaled version of) the eigenvector of $H$ corresponding to eigenvalue $\sqrt{2}^{-1}$ . In general, the nonzero values of $\{\phi (n)\colon n\in \mathbb{Z}\}$ , i.e. , $\left(\begin{array}{c}\phi (0)\\ \phi (1)\\ \dots \\ \phi (N-1)\end{array}\right)$ , can be calculated by appropriately scaling the eigenvector of the $N$ x $N$ row-decimated convolution matrix $H$ corresponding to the eigenvalue $\sqrt{2}^{-1}$ . It can be shown that this eigenvector must be scaled so that $\sum_{n=0}^{N-1} \phi (n)=1$ .
2. Given $\{\phi (n)\colon n\in \mathbb{Z}\}$ , we can use the scaling equation to determine $\{\phi (\frac{n}{2})\colon n\in \mathbb{Z}\}$ :
   $\phi (\frac{m}{2})=\sqrt{2}\sum_{n=0}^{N-1} h(n)\phi (m-n)$
   This produces the $2N-1$ non-zero samples $\{\phi (0), \phi (1/2), \phi (1), \phi (3/2), \dots , \phi (N-1)\}$ .
3. Given $\{\phi (\frac{n}{2})\colon n\in \mathbb{Z}\}$ , the scaling equation can be used to find $\{\phi (\frac{n}{4})\colon n\in \mathbb{Z}\}$ :
   $\phi (\frac{m}{4})=\sqrt{2}\sum_{n=0}^{N-1} h(n)\phi (\frac{m}{2}-n)=\sqrt{2}\sum h(\frac{p}{2})\phi (\frac{m-p}{2})=\sqrt{2}\sum h_{\uparrow 2}(p){\phi }_{\frac{1}{2}}(m-p)$
   where $h_{\uparrow 2}(p)$ denotes the impulse response of $H(z^2)$ , i.e. , a 2-upsampled version of $h(n)$ , and where ${\phi }_{\frac{1}{2}}(m)=\phi (\frac{m}{2})$ . Note that $\{\phi (\frac{n}{4})\colon n\in \mathbb{Z}\}$ is the result of convolving $h_{\uparrow 2}(n)$ with $\{{\phi }_{\frac{1}{2}}(n)\}$ .
4. Given $\{\phi (\frac{n}{4})\colon n\in \mathbb{Z}\}$ , another convolution yields $\{\phi (\frac{n}{8})\colon n\in \mathbb{Z}\}$ :
   $\phi (\frac{m}{8})=\sqrt{2}\sum_{n=0}^{N-1} h(n)\phi (\frac{m}{4}-n)=\sqrt{2}\sum h_{\uparrow 4}(p){\phi }_{\frac{1}{4}}(m-p)$
   where $h_{\uparrow 4}(n)$ is a 4-upsampled version of $h(n)$ and where ${\phi }_{\frac{1}{4}}(m)=\phi (\frac{m}{4})$ .
5. At the ${\ell }^{\mathrm{th}}$ stage, $\{\phi (\frac{n}{2^{\ell }})\}$ is calculated by convolving the result of the ${\ell -1}^{\mathrm{th}}$ stage with a $2^{(\ell -1)}$ -upsampled version of $h(n)$ :
   ${\phi }_{\frac{1}{2^{\ell }}}(m)=\sqrt{2}\sum h_{\uparrow 2^{\ell -1}}(p){\phi }_{\frac{1}{2^{\ell -1}}}(m-p)$

In [link] we show steps 1 through 5 of the cascade algorithm, as well as step 10, using Daubechies'db2 coefficients (for which $N=4$ ).