The Pyramid Algorithm

The MSA measuring process starts with the acquisition of a signal as an element in the central (``fiducial'', ``reference'') vector space $\mathbf{V}_0$ . This means that a signal

$$f(t)=\sum_{\ell=-\infty}^\infty c_\ell^0\phi(t-\ell)\in \mathbf{V}_0$$

is acquired in the form of a square summable sequence of numbers

$$\{c_\ell^0\}= \left\{ \langle\phi(u-\ell),f(u)\rangle\right\},~~~\ell=0,\pm 1,\cdots$$

The problem is to determine the representation of the signal in each of the subsequent (``lower resolution'') approximation spaces $\mathbf{V}_0 \supset \mathbf{V}_1\supset \mathbf{V}_2\supset \cdots$ , i.e. find

$$\{c_\ell^1\},\{c_\ell^2\},\cdots$$

such that

$$\sum_{\ell=-\infty}^\infty c_\ell^k\phi(t-\ell)=P_{\mathbf{V}_k}f(t)$$

is the least squares projection of $f(t)$ onto $\mathbf{V}_k$ for $k=1,2,\cdots$ . This turns out to be an iterative process which terminates after a finite number of steps.

The key observation which makes this process so powerful and appealing is that the relationship between two adjacent resolution spaces, say $\mathbf{V}_k$ and $\mathbf{V}_{k+1}$ , is independent of the order $k$ .

Given the fact that $\{\mathbf{V}_k:k=0,\pm 1,\cdots\}$ is a MSA and that $\phi(t)$ is the corresponding scaling function, we know that

• for fixed integer $k$
  $$\{ \sqrt{2^{-k}}\,\phi(2^{-k}t-\ell):~l=0,\pm 1,\cdots \}$$
  is an o.n. basis for $\mathbf{V}_k$ , and that
• each of the basis elements $\sqrt{2^{-(k+1)}}\,\phi(2^{-(k+1)}t-\ell')$ for $\mathbf{V}_{k+1}$ also belongs to $\mathbf{V}_k$ .

Consequently, each such basis element can be expanded uniquely in terms of the $\mathbf{V}_k$ -basis

$$\phi(2^{-(k+1)}t-\ell')=\sum_{\ell=-\infty}^\infty \phi(2^{-k}t-\ell)~ 2^{-k}\langle\phi(2^{-k}u-\ell),\phi(2^{-(k+1)}u-\ell')\rangle$$ (2108)

By changing variables in the inner product integral one finds that

$$2^{-k}\langle\phi(2^{-k}u-\ell),\phi(2^{-(k+1)}u-\ell')\rangle \equiv 2^{-k}\int\limits_{-\infty}^\infty \overline{\phi}(2^{-k}u-\ell)\phi(2^{-(k+1)}u-\ell')du$$

$$=\int\limits_{-\infty}^\infty \overline{\phi}(u-\ell)\phi(2^{-1}u-\ell')du$$

$$=\int\limits_{-\infty}^\infty \overline{\phi}\left(u-(\ell-2\ell')\right)\phi(2^{-1}u)du$$

$$\equiv \sqrt{2}~h_{\ell-2\ell'}$$

Exercise 26.4 (ORTHONORMALITY)

a) Point out why this inner product is the $(\ell,\ell')$ th entry of the $\sqrt{2}$ -multiple of a unitary matrix, which is independent of $k$ .

b) Show that $\sum_{\ell=-\infty}^\infty \overline{h}_\ell h_{\ell-2\ell'} =\delta_{0\ell'}$ .

When one computes the (complex) inner product of $f$ with both sides of Eq.(2.108), one obtains

$$\underbrace{ \langle\sqrt{2^{-(k+1)}}\phi(2^{-(k+1)}u-\ell'),f(u)\rangle }_{c_{\ell'}^{k+1}} = \sum_{\ell=-\infty}^\infty \langle\sqrt{2^{-(k+1)}}\phi(2^{-(k+1)}u-\ell'), \sqrt{2^{-k}}\phi(2^{-k}u-\ell)\rangle$$

$$~~~~~~~~~~~~\times\langle\sqrt{2^{-k}}\phi(2^{-k}u-\ell'),f(u)\rangle$$

$$= \sum_{\ell=-\infty}^\infty \underbrace{ \langle\sqrt{2^{-k}}\phi(2^{-k}u-\ell),f(u)\rangle }_{c_{\ell}^{k}} ~\overline{h}_{\ell-2\ell'}$$

Thus, by setting $\overline{h}_{\ell-2\ell'}\equiv\tilde{h}_{2\ell'-\ell}$ one has

$$\boxed{ c_{\ell'}^{k+1}=\sum_{\ell=-\infty}^\infty \tilde{h}_{2\ell'-\ell}~c_{\ell}^{k} }$$ (2109)

The sum on the r.h.s. is the discrete convolution of $\{ \tilde{h}_\ell \}$ and $\{ c_\ell^k \}$ . It shows that the discrete approximation

$$\{ c_\ell^{k+1} \}= \{ \langle\sqrt{2^{-(k+1)}} \phi(2^{-(k+1)} u-\ell),f(u)\rangle :~\ell=0,\pm 1,\cdots \}$$

of $f$ can be computed from $\{ c_\ell^k \}$ by convolving it with $\{ \tilde{h}_\ell \}$ , and then keeping only every other sample from the result. Thus, if one starts out with a discrete approximation $\{ c_\ell^k \}$ which represents $f$ by means of a finite number of samples, then the next discrete approximation is represented by only half as many samples. After a sufficient number of such iterative steps the process stops because one has run out of samples. All successive discrete approximations of $f$ are merely sequences of zeros. This iterative algorithm is known as the pyramid algorithm first introduced by Stephane Mallat[#!StephaneMallat1!#]. It is a rather efficient algorithm because it terminates after only

$$\log_2(\char93 \textrm{ of sampled values of }f)~.$$

iterations.