The Fast (Lifting) Wavelet Transform is a mathematical algorithm designed to turn a waveform or signal in the time domain into a sequence of coefficients based on an orthogonal basis of small finite waves, or wavelets. Mathematics is the study of quantity, structure, space and change. ... Flowcharts are often used to represent algorithms. ... Waveform quite literally means the shape and form of a signal, such as a wave moving across the surface of water, or the vibration of a plucked string. ... Time-domain is a term used to describe the analysis of mathematical functions, or real-life signals, with respect to time. ... This is a page about mathematics. ... In mathematics, an orthonormal basis of an inner product space V(i. ... All wavelet transforms consider a function (taken to be a function of time) in terms of oscillations which are localised in both time and frequency. ...

It has as theoretical foundation the device of a finitely generated, orthogonal multiresolution analysis (MRA). In the terms given there, one selects a sampling scale J with sampling rate of 2^J per unit interval, and projects the given signal f onto the space V_J; in theory by computing the scalar products A multiresolution analysis (MRA) or multiscale approximation (MSA) is the design method of most of the practically relevant discrete wavelet transforms (DWT) and the justification for the algorithm of the fast wavelet transform (FWT). ... The sampling frequency or sampling rate defines the number of samples per second taken from a continuous signal to make a discrete signal. ... In mathematics, the dot product (also known as the scalar product and the inner product) is a sesquilinear function (·) : V × V → F, where V is a vector space over the field F, having some further properties. ...

where φ is the scaling function of the chosen wavelet transform; in praxis by any suitable sampling procedure under the condition, that the signal is highly oversampled, so

is the orthogonal projection or at least some good approximation of the original signal in V_J. In geometry, an orthogonal projection of a k-dimensional object onto a d-dimensional hyperplane (d < k) is obtained by intersections of (k − d)- dimensional hyperplanes drawn through the points of an object orthogonally to the d-hyperplane. ...

The MRA is characterised by its scaling sequence

or, as Z-transform,

and its wavelet sequence In mathematics and signal processing, the Z-transform converts a discrete time domain signal, which is a sequence of real numbers, into a complex frequency domain representation. ...

or

(some coefficients might be zero). Those allow to compute the wavelet coefficients , at least some range k=M,...,J-1, without having to approximate the integrals in the corresponding scalar products. Instead, one can directly, with the help of convolution and decimation operators, compute those coefficients from the first approximation s^(J).

Forward DWT

One computes recursively, starting with the coefficient sequence s^(J) and counting down from k=J-1 down to some M<J, In mathematics and computer science, recursion is a particular way of specifying (or constructing) a class of objects (or an object from a certain class) with the help of a reference to other objects of the class: a recursive definition defines objects in terms of the already defined objects of...

single application of a wavelet filter bank, with filters g=a^*, h=b^*

or

and Image File history File links Discrete wavelet transform. ... Image File history File links Discrete wavelet transform. ...

or ,

for k=J-1,J-2,...,M and all . In the Z-transform notation:

recursive application of the filter bank

• The downsampling operator reduces an infinite sequence, given by its Z-transform, which is a formal Laurent-series, to the sequence of the coefficients with even indices, .
• The starred Laurent-polynomial a ^* (Z) denotes the adjoint filter, it has time-reversed adjoint coefficients, . (The adjoint of a real number being the number itself, of a complex number its conjugate, of a real matrix the transposed matrix, of a complex matrix its hermitian adjoint).
• Multiplication is polynomial multiplication, which is equivalent to the convolution of the coefficient sequences.

It follows that Image File history File links wavelet filter bank. ... Image File history File links wavelet filter bank. ... In mathematics and signal processing, the Z-transform converts a discrete time domain signal, which is a sequence of real numbers, into a complex frequency domain representation. ...

is the orthogonal projection of the original signal f or at least of the first approximation P_J[f](x) onto the subspace V_k, that is, with sampling rate of 2^k per unit interval. The difference to the first approximation is given by In mathematics, if a set with certain properties is called a space, then a subset of which with same properties is usually called a subspace. ...

,

where the difference or detail signals are computed from the detail coefficients as

,

with ψ denoting the mother wavelet of the wavelet transform.

Inverse DWT

Given the coefficient sequence s^(M) for some M<J and all the difference sequences d^(k), k=M,...,J-1, one computes recursively

or

for k=J-1,J-2,...,M and all . In the Z-transform notation:

• The upsampling operator creates zero-filled holes inside a given sequence. That is, every second element of the resulting sequence is an element of the given sequence, every other second element is zero or . This linear operator is, in the Hilbert space , the adjoint to the downsampling operator .

In mathematics, a Hilbert space is an inner product space that is complete with respect to the norm defined by the inner product. ...

External links

A comprehensive introduction to the Fast Lifting Wavelet Transform

I. Daubechies, W. Sweldens: Factoring Wavelet Transforms into Lifting Steps