Factoring Wavelet Transforms into Lifting Steps


Ingrid Daubechies       Wim Sweldens


Abstract: This paper is essentially tutorial in nature. We show how any discrete wavelet transform or two band subband filtering with finite filters can be decomposed into a finite sequence of simple filtering steps, which we call lifting steps but that are also known as ladder structures. This decomposition corresponds to a factorization of the polyphase matrix of the wavelet or subband filters into elementary matrices. That such a factorization is possible is well-known to algebraists (and expressed by the formula SL(n;R[z,1/z]) = E(n; R[z,1/z])); it is also used in linear systems theory in the electrical engineering community. We present here a self-contained derivation, building the decomposition from basic principles such as the Euclidean algorithm, with a focus on applying it to wavelet filtering. This factorization provides an alternative for the lattice factorization, with the advantage that it can also be used in the biorthogonal, i.e, non-unitary case. Like the lattice factorization, the decomposition presented here asymptotically reduces the computational complexity of the transform by a factor two. It has other applications, such as the possibility of defining a wavelet-like transform that maps integers to integers.

Status: J. Fourier Anal. Appl., Vol. 4, Nr. 3, pp. 247-269, 1998.

Notes:
April 2002:
Some typo on page 2 and 3 (mostly switching x_e and x_o) were corrected. Thanks to Yao-Tien Chen from the National Central University Taiwan for pointing them out.

Download: PDF v3.0 (.pdf) (240K).

BiBTeX entry: 


   @article{ds:factor,
    author = {I. Daubechies and W. Sweldens},
    title = {Factoring Wavelet Transforms into Lifting Steps},
    journal = {J. Fourier Anal. Appl.},
    volume = 4,
    number = 3,
    pages = {245-267},
    year = {1998}		  
   }