Factoring wavelet transforms into lifting steps (Q1271489)

Given a signal \((x_k)_{k \in Z}\), we may split it into even \(x_e = (x_{2k})\) and odd \(x_o = (x_{2k+1})\) components. A lifting step is defined to be a transformation of the form \(x \mapsto (x_o, x_e - P(x_o))\), where \(P(x_o)\) is a linear predictor for the even component based on the odd component. (For instance, one could take \(P(x_o)_{2k} = (x_{2k-1} + x_{2k+1})/2\)). A dual lifting step is a transformation of the form \((x_o,d) \mapsto (x_o + U(d), d)\), where \(U(d)\) is an update operator to the odd components based upon the detail \(d = x_e - P(x_o)\). (For instance, one can take \(U(d)_{2k} = (d_{2k-1} + d_{2k+1})/4)\). In this paper the authors show that any finite impulse response (FIR) filter bank or wavelet transform can be factored into a sequence of lifting steps and dual lifting steps, each of which is also given by an FIR filter. The method of proof relies upon the z-transform and then a factorization of a Laurent polynomial-valued matrix into elementary matrices by means of the Euclidean algorithm.