Lifting scheme

Remarks

The inverse formulas hold for every choice of $P$ and $U$, since each step adds to one half of the data a function of the other half only. So invertibility does not depend on the operators, and $P$ and $U$ may even be nonlinear, for instance include rounding to integers.

Example (Haar): take $P(e)_k = e_k$ and $U(d)_k = d_k/2$. Then $d_k = x_{2k+1} - x_{2k}$ and $s_k = x_{2k} + (x_{2k+1} - x_{2k})/2 = (x_{2k} + x_{2k+1})/2$. This is the Haar transform up to constant factors: the orthonormal Haar step gives $\sqrt{2}\, s_k$ and $-d_k/\sqrt{2}$.

Example (CDF 5/3): take $P(e)_k = (e_k + e_{k+1})/2$ and $U(d)_k = (d_{k-1} + d_k)/4$. This computes the 5/3 biorthogonal wavelet transform; with rounding inside $P$ and $U$ it maps integers to integers and is the lossless transform of JPEG 2000.

Non-example: a step $o \mapsto o - P(o)$ that modifies the odd samples using the odd samples themselves is not a lifting step. It need not be invertible: with $P = \id$ it sends every odd part $o$ to $0$, so $o$ cannot be recovered.

Every discrete wavelet transform given by a two-channel perfect-reconstruction filter bank with finite filters can be factored into finitely many lifting steps and a scaling.