FACTORING WAVELET TRANSFORMS INTO LIFTING STEPS

This article is essentially tutorial in nature. We show how any discre te wavelet transform or two band subband filtering with finite filters can be decomposed into a finite sequence of simple filtering steps, w hich we call lifting steps but that are also known as ladder structure s. This decomposition corresponds to a factorization of the polyphase matrix of the wavelet or subband filters into elementary matrices. Tha t such a factorization is possible is well-known to algebraists land e xpressed 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 comm unity. We present here a self-contained derivation, building the decom position from basic principles such as the Euclidean algorithm, with a focus on applying it to wavelet filtering. This factorization provide s an alternative for the lattice factorization, with the advantage tha t it can also be used in the biorthogonal, i.e., non-unitary case. Lik e the lattice factorization, the decomposition presented here asymptot ically reduces the computational complexity of the transform by a fact or two. Ir has other applications, such as the possibility of defining a wavelet-like transform that maps integers to integers.