Lifting scheme

Summary

The lifting scheme is a way to build and compute wavelet transforms by a sequence of simple, invertible steps. A signal is split into its even and odd samples. The odd samples are predicted from the even ones, and the even ones are updated from the prediction errors. Every step can be undone by reversing its sign, so perfect reconstruction is automatic. The scheme can cut the cost of many fast wavelet transforms by up to about one half. It works in place, gives integer-to-integer transforms, and extends to irregular grids.