---
tag: A00DAT34F9
kind: definition
name: Lifting scheme
msc: [65T60, 42C40, 94A12]
defines: AF9NY73QHJ
uses: [P3H4MMC4ZH]
sources:
  - url: https://en.wikipedia.org/wiki/Lifting_scheme
---

## Definition

Let $x = (x_n)_{n \in \Z}$ be a sequence of real numbers.
One *lifting stage* with operators $P$ and $U$ on sequences, usually linear filters, consists of three steps:

1. Split: $e_k = x_{2k}$ and $o_k = x_{2k+1}$ for $k \in \Z$.
2. Predict: $d = o - P(e)$.
3. Update: $s = e + U(d)$.

The output is the pair $(s, d)$ of approximation and detail sequences.
The *lifting scheme* computes a wavelet transform as a composition of such stages.
A stage may contain several predict and update steps in alternation.
At the end, $s$ and $d$ may be multiplied by constants.
The inverse of one stage is $e = s - U(d)$, then $o = d + P(e)$, then the merging of $e$ and $o$ into $x$.

## 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|P3H4MMC4ZH]] given by a two-channel perfect-reconstruction filter bank with finite filters can be factored into finitely many lifting steps and a scaling.

## Explanations

### L1 human

A lifting stage splits a signal into even and odd samples, records how badly the evens predict the odds, and then corrects the evens.
Each step only adds something to one half, computed from the other half, so it can always be undone.