Fast wavelet transform

Summary

The fast wavelet transform is the recursive filter-bank algorithm that computes the discrete wavelet transform of a signal. At each level it convolves the current approximation with a low-pass and a high-pass filter and keeps every second output. For a signal of length $N$ and filters of fixed length, it uses $O(N)$ operations, which is even faster than the fast Fourier transform. It is also known as Mallat's algorithm, and it rests on the structure of a multiresolution analysis.