Fast Wavelet Transform (FWT) and Filter Bank

As shown before, the discrete wavelet transform of a discrete signal ${\bf x}=[x[0],\cdots,x[N-1]]^T$ is the process of getting the coefficients:

$$W_{\varphi}[j_0,k]=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1} x[m] \v... ...m] 2^{j_0/2}\varphi[2^{j_0} m-k], \;\;\;\;\mbox{(for all $k$)}$$

$$W_{\psi}[j,k]=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1} x[m] \psi_{j... ...2}\psi[2^j m-k], \;\;\;\;\mbox{(for all $k$ and all $j>j_0$)}$$

where the basis scaling and wavelet functions are respectively

$$\varphi_{j,k}[m]=2^{j/2}\varphi[2^j m-k]\;\;\;\;\mbox{and}\;\;\;\; \psi_{j,k}[m]=2^{j/2}\psi[2^j m-k]$$

Recall that both the scaling and wavelet functions can be expanded in terms of the basis scaling functions of the next higher resolution:

$$\begin{array}{l} \varphi[m]=\sum_l h_{\varphi}[l]\sqrt{2} \v... ... \psi[m]=\sum_l h_{\psi}[l]\sqrt{2} \varphi[2m-l] \end{array}$$

We now consider a fast algorithm to obtain the coefficients $W_{\varphi}[j,k]$ and $W_{\psi}[j,k]$ of different scales $j$. Consider first the scaling function $\varphi[m]$. Replacing $m$ by $2^j m-k$ (scaled by $2^j$ and translated by $k$), we get

$$\varphi[2^jm-k]=\sum_l h_{\varphi}[l]\sqrt{2} \varphi[2(2^jm-k)-l] =\sum_l h_{\varphi}[l]\sqrt{2} \varphi[2^{j+1}m-2k-l]$$

We then let $n=2k+l$ i.e. $l=n-2k$, the above becomes

$$\varphi[2^jm-k]=\sum_n h_{\varphi}[n-2k]\sqrt{2} \varphi[2^{j+1}m-n]$$

Similarly, the wavelet function can also be expanded:

$$\psi[2^jm-k]=\sum_n h_{\psi}[n-2k]\sqrt{2} \varphi[2^{j+1}m-n]$$

This wavelet function is identical to the one used in the discrete wavelet transform above, which can be replaced by the right-hand side of the equation:

$$W_{\psi}[j,k] = \frac{1}{\sqrt{N}}\sum_{m=0}^{N-1} x[m] 2^{j/2}\psi[2^j m-k] =\fr... ...um_{m=0}^{N-1} x[m] 2^{j/2} [\sum_n h_{\psi}[n-2k]\sqrt{2} \varphi[2^{j+1}m-n]]$$

$$= \sum_n h_{\psi}[n-2k][\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1} x[m] 2^{(j+1)/2} \varphi(2^{j+1}m-n)]$$

Note that the expression inside the brackets happens to be the wavelet transform for the coefficient of scale $j+1$:

$$W_{\psi}[j+1,k]=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}x[m]2^{(j+1)/2}\varphi(2^{j+1}m-n)$$

therefore we have a recursive relation between the wavelet transform coefficients of two consecutive scale levels $j$ and $j+1$:

$$W_{\psi}[j,k]=\sum_n h_{\psi}[n-2k]W_{\varphi}[j+1,n]$$

and the same is true to the scaling function:

$$W_{\varphi}[j,k]=\sum_n h_{\varphi}[n-2k]W_{\varphi}[j+1,n]$$

Comparing these equations with a discrete convolution:

$$y[k]=h[k]*x[k]=\sum_n h[k-n]x[n]$$

we see that the wavelet transform coefficients $W_{\varphi}[j,k]$ and $W_{\psi}[j,k]$ at the jth scale can be obtained from the coefficients $W_{\varphi}[j+1,k]$ and $W_{\psi}[j+1,k]$ at the (j+1)th scale by:

• Convolution with time-reversed $h_{\varphi}$ or $h_{\psi}$;
• Sub-sampling to get every other samples in the convolution.

We can therefore write

$$\begin{array}{l} W_{\psi}[j,k]=h_{\psi}[-n]*W_{\varphi}[j+1,... ...rphi}[-n]*W_{\varphi}[j+1,n]\vert _{n=2k,k\le 0} \end{array}$$

Based on these two equations, all wavelet and scaling coefficients $W_{\psi}[j,k]$ and $W_{\varphi}[j,k]$ of a given signal ${\bf x}$ can be obtained recursively from the coefficients $W_{\psi}[J,k]$ and $W_{\varphi}[j,k]$ at the highest resolution level $j=J$ (with maximum details), i.e., the $N$ data points $x[m]$ ( $m=0,\cdots,N-1$) directly sampled from the signal $x(t)$. As a member of space $V_J$, these discrete samples can be written as a linear combination of the scaling basis functions $\varphi_{J,k}[m]$:

$$x[m]=\sum_k W_{\varphi}[J,k] \varphi_{J,k}[m]$$

If we let the kth basis function be a unit pulse at the kth sampling time, i.e., $\varphi_{J,k}[m]=\delta[k-m]$ (same as the ith component of a unit vector ${\bf e}_j$ in N-dimensional vector space is $e_{ij}=\delta[i-j]$), then the kth coefficient $W_{\varphi}[J,k]$ is the same as the kth sample of the function $x(t)$. I.e., $W_{\varphi}[J,k]=x(k)$, from which the scaling and wavelet coefficients of the lower scales $j<J$ can be obtained by the subsequent filter banks.

Inverse Wavelet Transform

As the forward wavelet transform - finding the transform coefficients $W_{\varphi}$ and $W_{\psi}$ from a given function $x(t)$ - can be implemented by the analysis filter bank, the inverse wavelet transform - reconstructing the function $x(t)$ from the coefficients $W_{\varphi}$ and $W_{\psi}$ - can be implemented by the synthesis filter bank.

Complexity of FWT

The computation cost of the fast wavelet transform (FWT) is the convolutions carried out in each of the filters. The number of data samples in the convolution is halved after each sub-sampling, therefore the total complexity is:

$$O(N+\frac{N}{2}+\frac{N}{4}+\frac{N}{8}+\cdots+1)=O(N)$$

i.e., the FWT has linear complexity.

The system shown in the figure above is called a filter bank and is further discussed here

A detailed discussion about Matlab implementaton can be found on this MathWorks webpage.