Wavelets and their Applications

Chapter 3

From Wavelet Bases to the Fast Algorithm

3.1. Introduction

Stéphane Mallat [MAL 89] proposed the fast algorithm of decomposition reconstruction for the discrete wavelet transform at the end of the 1980s. He thus established the link between orthonormal wavelet bases, whose mathematical development was then recent, and traditional filter banks in signal processing.

This unifying point of view brought the two communities closer, enabled an increased development of applications for signals or images and aroused theoretical interest. For example, the fruitful filters approach led to wavelet synthesis or compression.

Moreover, two unexpected features have to be pointed out: the algorithm is remarkably simple and its complexity grows only linearly with the size of data, i.e. it is lower than that of the fast Fourier transform. This aspect is obviously crucial for applications.

The chapter begins with the discrete wavelet transform algorithm of sampled signals (shortened to DWT for discrete wavelet transform). It is a purely discrete framework, in the sense that instead of a function we decompose a finite sequence, using finite impulse response filters. In the language of signal processing, it is the implementation of two-channel [EST 77] filter banks and filter banks with perfect reconstruction (this point of view will be developed in the second part of Chapter 5).

Then we consider the justification of the algorithm coming back to the framework of continuous time signals provided ...