This article 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, z
−1])=
E(n;
R[z, z
−1])); 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.
Math Subject Classifications 42C15 - 42C05 - 19-02
Keywords and Phrases Wavelet - lifting - elementary matrix - Euclidean algorithm - Laurent polynomial
Communicated by John J. Benedetto
Research Tutorial
Acknowledgements and Notes. Page 264.