0.2 The filtered transform

Introduction

We saw in a previous section an example of a scaling function $\varphi ,$ and we outlined how to construct $\psi$ (also called the mother wavelet) starting from $\varphi$ (the father wavelet). Suppose now we have at our disposal $\left\{{\varphi }_{j,k}\right\}$ and $\left\{{\psi }_{j,k}\right\}.$ In fact, it is sufficient for our purpose to know the value of these functions at dyadic points $2^{-j}k,j\in \mathrm{Z}\mathrm{Z},k\in \mathrm{Z}\mathrm{Z}.$ We would like to compute in an efficient way the wavelet representation described in Homogeneous and inhomogeneous representation of f , that is, we would like to have a fast algorithm to compute the wavelet coefficients.

Filter algorithm-fast wavelet transform

We will still use the relationship between the functions spaces $V_j$ and $W_j$ to find a fast wavelet transform (FWT). We start by recalling that, since both the scaling function $\varphi \in V_0$ and the wavelet $\psi \in W_0$ are in $V_1,$ and since $V_1$ is generated by ${\varphi }_{1,k}=\sqrt{2}\varphi (2x-k),k\in \mathrm{Z}\mathrm{Z},$ there exist two sequences $\left\{h_k\right\}$ and $\left\{g_k\right\}\in l^2$ such that

for all $x\in \mathrm{I}\mathrm{R}.$ On the other hand, we know that $V_1=V_0\oplus W_0$ and as we consider the orthogonal case, it follows immediately that :

These two equations [link] and [link] can be combined into a single formula:

which is called the “decomposition relation” of $\varphi$ and $\psi .$

Note that, in the bi-orthogonal case there are four sequences in $l^2$ instead of two (denoted here by $\left\{h_k\right\}$ and $\left\{g_k\right\}$ ): we have two sequences for the 2-scales relations [link] , [link] , and two others for the decomposition relations [link] , [link] . In the following algorithm, we drop the normalisation constant. Suppose that we want to decompose $f$ as a sum of wavelets and that we have computed, or are given, the inner products of $f$ with ${\varphi }_{J,k},$ where $J$ is the finest scale we can work on. We denote these inner products by $c^J.$ Now, our task is to compute $c_k^j$ and $d_k^j,j<J,$ where

Decomposition algorithm

By combining [link] , [link] and [link] , we get (see [link] ):

Observe that both ${\mathbf{c}}^{\mathbf{j}-\mathbf{1}}$ and ${\mathbf{d}}^{\mathbf{j}-\mathbf{1}}$ are obtained from ${\mathbf{c}}^{\mathbf{j}}$ by “moving average” schemes, using the decomposition sequence as “weights”, with the exception that these moving averages are sampled only at the even integers. This is called downsampling.

Reconstruction algorithm

In the orthogonal case, the reconstruction algorithm follows easily from the relationships:

which gives:

Hence ${\mathbf{c}}^{\mathbf{j}+\mathbf{1}}$ is obtained from ${\mathbf{c}}^{\mathbf{j}}$ and ${\mathbf{d}}^{\mathbf{j}}$ by two moving average.

Mallat's algorithm

In the previous section, we assumed that we knew the coefficients

The question to ask is: how to compute these coefficients ? In Mallat's algorithm (see [link] ), we consider that the finestscale is constituted by the observations ${\left\{Y_k\right\}}_{k=1}^n$ themselves. To use the MRA presented above, these observations must be taken at equispaced points, i.e. we can write that

Moreover, we assume that $n$ (the number of observations) is a power of 2 : $n=2^J,$ with $J$ denoting the finest level.

Mallat's algorithm is based on the fact that, as $j$ tends to infinity, the support of ${\varphi }_{j,k}$ tends to become smaller and smaller. We have:

Hence Mallat considered that we can compute $c_k^J$ as:

The starting point of this algorithm is thus extremely simple: we just take as value for $c_k^J$ the whole set of observations. Thereafter, having constructed the filters $\left\{h_k\right\}\text{and}\left\{g_k\right\}$ (or, equivalently, having constructed $\varphi$ and $\psi$ ), we can compute a fast wavelet transform using the algorithm presented in the previous section.