Definition of the Subject
The objective of this entry is to give a concise introduction to the discrete wavelet transform (DWT) based on a technique called lifting. The lifting technique allows one to give an elementary, but rigorous, definition of the DWT, with modest requirements on the reader. A basic knowledge of linear algebra and signal processing will suffice. The lifting-based definition is equivalent to the usual filter bank-based definition of the DWT. The entry does not discuss applications in any detail. The reader is referred to other entries in this collection.
The DWT was introduced in the second half of the 1980s, through the work of Y. Meyer, I. Daubechies, S. Mallat, and many other researchers. The lifting technique was introduced by W. Sweldens in 1996, and the equivalence with the filter bank approach was established by I. Daubechies and W. Sweldens in an article published in 1998 (Daubechies and Sweldens 1998) but available in preprint form from 1996.
This entry is...
This is a preview of subscription content, log in via an institution to check access.
Abbreviations
- Lifting step:
-
An equation describing the transformation of an odd (even) sample of a signal by means of a linear combination of even (odd) samples, respectively. Changing an odd sample is sometimes called a prediction step, while changing an even sample is called an update step.
- Discrete wavelet transform (DWT):
-
Transformation of a discrete (sampled) signal into another discrete signal by means of a wavelet basis. The transform can be accomplished in a number of ways, typically either by a two-channel filter bank or by lifting steps.
- Filter bank:
-
A series of band-pass filters, which separates the input signal into a number of components, each with a distinct range of frequencies of the original signal.
- z-Transform:
-
A mapping of a vector x = {x[k]} to a function in the complex plane by
$$ X(z)={\displaystyle \sum_kx\left[k\right]{z}^{-k}}. $$For a vector with a finite number of nonzero entries, X(z) is a Laurent polynomial.
- Filter:
-
A linear map, which maps a signal x with finite energy to another signal with finite energy. In the time domain, it is given by convolution with a vector h, which in the frequency domain is equal to H(z)X(z). The vector h is called the impulse response (IR) of the filter (or sometimes the filter taps) and H(e jω) the transfer function (or sometimes the frequency response). If h is a finite sequence, then h is called a FIR (finite impulse response) filter. An infinite h is then called an IIR filter. We only consider FIR filters in this entry. We restrict ourselves to filters with real coefficients.
- Filter taps:
-
The entries in the vector that by convolution with a signal give a filtering of the signal. The filter taps are also called the impulse response of the filter.
- Laurent polynomial:
-
A polynomial in the variables z and z −1. Some examples: 3z −2 + 2z, z −3 − 2z −1, and 1 + z + z 3. The z-transform of a FIR filter h is a Laurent polynomial of the form
$$ H(z)={\displaystyle \sum_{k={k}_b}^{k_e}x\left[k\right]{z}^{-k}},{k}_b\le {k}_e. $$This is in contrast to ordinary polynomials, where we only have nonnegative powers of z. Assuming that h[k e] ≠ 0 and h[k b] ≠ 0, the degree of a Laurent polynomial is defined as |h| = k e − k b.
- Monomial:
-
A Laurent polynomial of degree 0, for example, 3z 7, z −8, or 12.
Bibliography
Daubechies I (1992) Ten lectures on wavelets. CBSM-NSF regional conference series in applied mathematics, vol 60. SIAM, Philadelphia
Daubechies I, Sweldens W (1998) Factoring wavelet transforms into lifting steps. J Fourier Anal Appl 4(3):245–267
Jensen A, la Cour-Harbo A (2001) Ripples in mathematics – the discrete wavelet transform. Springer, Heidelberg
Mallat S, Wavelet A (1998) Tour of signal processing. Academic, San Diego
Mulcahy C (1996) Plotting and scheming with wavelets. Math Mag 69(5):323–343
Oppenheim AV, Schafer R (1975) Digital signal processing. Prentice Hall, Upper Saddle River
Oppenheim AV, Schafer R, Buck JR (1999) Discrete-time signal processing. Prentice Hall, Upper Saddle River
Sweldens W (1996) The lifting scheme: a custom-design construction of biorthogonal wavelets. Appl Comput Harmon Anal 3(2):186–200
Sweldens W (1997) The lifting scheme: a construction of second generation wavelets. SIAM J Math Anal 29(2):511–546
Vetterli M, Kovačević J (1995) Wavelets and subband coding. Prentice-Hall, Englewood Cliffs
Vetterli M, Kovačević J (2007) Wavelets and subband coding, 2nd edn. http://waveletsandsubbandcoding.org. Accessed 5 Sept 2008
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer Science+Business Media New York
About this entry
Cite this entry
La Cour-Harbo, A., Jensen, A. (2013). Wavelets and the Lifting Scheme. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY. https://doi.org/10.1007/978-3-642-27737-5_588-3
Download citation
DOI: https://doi.org/10.1007/978-3-642-27737-5_588-3
Received:
Accepted:
Published:
Publisher Name: Springer, New York, NY
Online ISBN: 978-3-642-27737-5
eBook Packages: Springer Reference Physics and AstronomyReference Module Physical and Materials ScienceReference Module Chemistry, Materials and Physics