Next: 2D DWT Up: wavelets Previous: Discrete Wavelet Transform

# Fast Wavelet Transform (FWT) and Filter Bank

As shown before, the discrete wavelet transform of a discrete signal is the process of getting the coefficients:

where the basis scaling and wavelet functions are respectively

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

We now consider a fast algorithm to obtain the coefficients and of different scales . Consider first the scaling function . Replacing by (scaled by and translated by ), we get

We then let i.e. , the above becomes

Similarly, the wavelet function can also be expanded:

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:

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

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

and the same is true to the scaling function:

Comparing these equations with a discrete convolution:

we see that the wavelet transform coefficients and at the jth scale can be obtained from the coefficients and at the (j+1)th scale by:
• Convolution with time-reversed or ;
• Sub-sampling to get every other samples in the convolution.
We can therefore write

Based on these two equations, all wavelet and scaling coefficients and of a given signal can be obtained recursively from the coefficients and at the highest resolution level (with maximum details), i.e., the data points ( ) directly sampled from the signal . As a member of space , these discrete samples can be written as a linear combination of the scaling basis functions :

If we let the kth basis function be a unit pulse at the kth sampling time, i.e., (same as the ith component of a unit vector in N-dimensional vector space is ), then the kth coefficient is the same as the kth sample of the function . I.e., , from which the scaling and wavelet coefficients of the lower scales can be obtained by the subsequent filter banks.

Inverse Wavelet Transform

As the forward wavelet transform - finding the transform coefficients and from a given function - can be implemented by the analysis filter bank, the inverse wavelet transform - reconstructing the function from the coefficients and - 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:

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.

Next: 2D DWT Up: wavelets Previous: Discrete Wavelet Transform
Ruye Wang 2008-12-16