Discrete wavelet transform

The discrete wavelet transform (DWT) refers to wavelet transforms for which the wavelets are discretely sampled.

The first DWT was invented by Haar, a German mathematician. For an input represented by a list of $2^{n}$ numbers, the Haar wavelet transform may be considered to simply pair up input values, storing the difference and passing the sum. This process is repeated recursively, pairing up the sums to provide the next scale. Finally resulting in $2^{n}-1$ differences and one final sum. This simpleDWT illustrates the desirable properties of wavelets in general. Firstly, the discrete transform can be performed in $O(n)$ operations. Secondly, the transform captures not only some notion of the frequency content of the input, by examining it at different scales, but also captures temporal content, i.e. the times at which these frequencies occur. Combined, these two properties make the Fast Wavelet Transform (FWT) a tempting alternative to the conventional Fast Fourier Transform.

The most common set of discrete wavelet transforms were formulated by the Belgian mathematician Ingrid Daubechies in 1988. This formulation is based upon the use of recurrence relations to generate progressively finer discrete samplings of an implicit mother wavelet function, each resolution being twice that of the previous scale. In her seminal paper, Daubechies derives a family of wavelets, the first of which is the Haar wavelet. Interest in this field has exploded since then, with the development of many descendents to Daubechies' original family of wavelets.

Other forms of discrete wavelet transform include the non- or undecimated wavelet transform (where downsampling is omitted), the Newland transform (where an orthonormal basis of wavelets is formed from appropriately constructed top-hat filters in frequence-space). Wavelet packet transforms are also related to the discrete wavelet transform.

The discrete wavelet transform has a huge number of applications in science, engineering, mathematics and computer science. Most notably, the discrete wavelet transform is used for signal coding, where the properties of the transform are exploited to represent a discrete signal in a more redundant form, often as a preconditioning for data compression.