The Wavelet Lifting Scheme

At the beginning of my journey, I was naive. I didn't yet know that answers vanish as one continues to travel, that there is only further complexity, that there are still more interrelationships, and more questions.

Robert D. Kaplan, The Ends of the Earth: a journey to the frontiers of anarchy, Vintage Press, 1996

Wavelets and Their Applications

Wavelets have been applied in a wide range of areas. My interest in wavelets came from digital signal processing of non-stationary time series (see my web page Applying the Haar Wavelet Transform to Time Series Information). Data sets without obviously periodic components cannot be processed well using Fourier techniques. Wavelets allow complex filters to be constructed for this kind of data which can remove or enhance selected parts of the signal. There is a growing body of literature on wavelet techniques for noise reduction.

Wavelets have been used for data compression. For example, the United States FBI compresses their fingerprint data base using wavelets. Lifting scheme wavelets also form the basis of the emerging JPEG 2000 image compression standard.

Wavelet techniques have also been used in a variety of statistical applications, including signal variance estimation, frequency analysis and kernel regression.

The coverage of most of these topics requires a book length discussion and is way beyond the scope of these humble web pages.

What These Web Pages Contribute

There is a large and growing literature on wavelets ranging from papers in mathematical journals to applied areas like artificial intelligence (neural nets) and geology. Frequently mathematics papers deal with wavelets applied to an infinite series of data. This leaves a large gap between theory and practice. In the case of papers that apply wavelets, I often get the impression that many of the authors are using existing wavelet functions in Mathematica or MathLab. These articles often include the standard integral expression for wavelets on an infinite data series, but the complexities of wavelet implementation are not discussed.

The fact that the authors of a journal article applying wavelet analysis to the study of the geology of karsts, aquifers and water flow do not implement the wavelet algorithms themselves is understandable. I have spent months studying wavelets and I still feel that I have far to go. I am sure that there are are mathematical depths to wavelets that I will never understand. Compared with theoretical papers on wavelets, there is much less material on applying wavelets to real problems. As someone who has implemented wavelet algorithms in Java and C++, I have found the gap between theory and application frustrating. In the few cases where I have found wavelet software source code, it has provided little illumination. The software was not clearly written and I did not understand it until I already understood the wavelet algorithm that it implemented.

Wavelet techniques are remarkably powerful and general. Applying wavelet techniques is also surprisingly complicated (there are times when I find myself longing to the simplicity of the Fourier transform). I hope that this web page will fill some of the gap between wavelet theory and application. I am a software engineer with rather modest skills in mathematics. This web page provides an applied view of wavelet algorithms through the lens of the Lifting Scheme. I have tried to provide clearly written software that implements the algorithms I discuss.

The mathematically sophisticated may look at this web page as a "kindergarten" view of wavelets and mathematics. In most cases I list even simple algebraic steps in deriving an equation. This reflects the humble skills of the author of these web pages. For those who find the material on these web pages trivial, I suggest going directly to the wavelet literature where the reader may find far more sophistication.

Sadly this web page is drastically incomplete. In such a short discussion I cannot completely cover the wavelet mathematics which underlies these algorithms. To do so would require a book, not a web page or two. These web pages are best read along with the references listed at the end.

Perfect Reconstruction in an Finite World

One of the features of wavelets that is critical in areas like signal processing and compression is what is referred to in the wavelet literature as perfect reconstruction. A wavelet algorithm has perfect reconstruction when the inverse wavelet transform of the result of the wavelet transform yields exactly the original data set:

  IWT( WT( D ) ) = D
(Here IWT is the inverse wavelet transform and WT is the wavelet transform.)

If the wavelet literature is any guide, when mathematicians think about and write about wavelets equations, they think about wavelets applied to an infinite sequence of data. Many wavelet equations that have the property of perfect reconstruction for infinite data sequences do not have this property for finite data sequences. Since sound files, financial time series, images and other data sets to which wavelets are applied are finite this can be a problem. There are several methods proposed in the wavelet literature for dealing with the edges of finite data sets. See for example, my discussion of the Daubechies D4 wavelet transform.

The simplest wavelet algorithm that shows perfect reconstruction is the Haar wavelet algorithm. However, Haar wavelets can miss detail and do not always represent change at all resolution scales. See Limitations of the Haar Wavelet Transform.

Relative to the Haar wavelet algorithm, the Daubechies D4 algorithm shows better multi-scale resolution, at the cost of a more complex algorithm. Wim Sweldens' tutorial Building Your Own Wavlets at Home (see references, below) showed how Haar wavelets could be expressed in Lifting Scheme form and extended to provide accurate multiscale resolution. The Lifting Scheme provides a simpler view of many wavelet algorithms. The Lifting Scheme provides the basis for the book Ripples in Mathematics (referenced below). This book is the primary reference for these web pages.

Lifting Scheme Sub-pages

References

Web Links

Local Links


Ian Kaplan