Fast wavelet transform

The Fast Wavelet Transform is a mathematical algorithm designed to turn a waveform or signal in the time domain into a sequence of coefficients based on an orthogonal basis of small finite waves, or wavelets.

It has as theoretical foundation the device of a finitely generated, orthogonal multiresolution analysis (MRA). In the terms given there, one selects a sampling scale J with sampling rate of 2^J per unit interval, and projects the given signal f onto the space $V_{J}$; in theory by computing the scalar products

$s_{n}^{(J)}:=2^{J}\langle f(t),\phi (2^{J}t-n)\rangle ,$

where $\phi$ is the scaling function of the chosen wavelet transform; in praxis by any suitable sampling procedure under the condition, that the signal is highly oversampled, so

$P_{J}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(J)}\,\phi (2^{J}x-n)$

is the orthogonal projection or at least some good approximation of the original signal in $V_{J}$.

The MRA is characterised by its scaling sequence

$a=(a_{-N},\dots ,a_{0},\dots ,a_{N})$ or, as Z-transform, $a(Z)=\sum _{n=-N}^{N}a_{n}Z^{n}$

and its wavelet sequence

$b=(b_{-N},\dots ,b_{0},\dots ,b_{N})$ or $b(Z)=\sum _{n=-N}^{N}b_{n}Z^{n}$

(some coefficients might be zero). Those allow to compute the wavelet coefficients $d_{n}^{(k)}$, at least some range k=M,...,J-1, without having to approximate the integrals in the corresponding scalar products. Instead, one can directly, with the help of convolution and decimation operators, compute those coefficients from the first approximation $s^{(J)}$.

Forward DWT

One computes recursively, starting with the coefficient sequence $s^{(J)}$ and counting down from k=J-1 down to some M<J,

single application of a wavelet filter bank, with filters g=a^*, h=b^*

$s_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}a_{m}s_{2n+m}^{(k+1)}$ or $s^{(k)}(Z):=(\downarrow 2)(a^{*}(Z)\cdot s^{(k+1)}(Z))$

and

$d_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}b_{m}s_{2n+m}^{(k+1)}$ or $d^{(k)}(Z):=(\downarrow 2)(b^{*}(Z)\cdot s^{(k+1)}(Z))$,

for k=J-1,J-2,...,M and all $n\in \mathbb {Z}$. In the Z-transform notation:

recursive application of the filter bank

• The downsampling operator $(\downarrow 2)$ reduces an infinite sequence, given by its Z-transform, which is simply a Laurent series, to the sequence of the coefficients with even indices, $(\downarrow 2)(c(Z))=\sum _{k\in \mathbb {Z} }c_{2k}Z^{k}$.
• The starred Laurent-polynomial $a^{*}(Z)$ denotes the adjoint filter, it has time-reversed adjoint coefficients, $a^{*}(Z)=\sum _{-N}^{N}a_{n}^{*}Z^{-n}$. (The adjoint of a real number being the number itself, of a complex number its conjugate, of a real matrix the transposed matrix, of a complex matrix its hermitian adjoint).
• Multiplication is polynomial multiplication, which is equivalent to the convolution of the coefficient sequences.

It follows that

$P_{k}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(k)}\,\phi (2^{k}x-n)$

is the orthogonal projection of the original signal f or at least of the first approximation $P_{J}[f](x)$ onto the subspace $V_{k}$, that is, with sampling rate of 2^k per unit interval. The difference to the first approximation is given by

$P_{J}[f](x)=P_{k}[f](x)+D_{k}[f](x)+\dots +D_{J-1}[f](x)$,

where the difference or detail signals are computed from the detail coefficients as

$D_{k}[f](x):=\sum _{n\in \mathbb {Z} }d_{n}^{(k)}\,\psi (2^{k}x-n)$,

with $\psi$ denoting the mother wavelet of the wavelet transform.

Inverse DWT

Given the coefficient sequence $s^{(M)}$ for some M<J and all the difference sequences $d^{(k)}$, k=M,...,J-1, one computes recursively

$s_{n}^{(k+1)}:=\sum _{k=-N}^{N}a_{k}s_{2n-k}^{(k)}+\sum _{k=-N}^{N}b_{k}d_{2n-k}^{(k)}$ or $s^{(k+1)}(Z)=a(Z)\cdot (\uparrow 2)(s^{(k)}(Z))+b(Z)\cdot (\uparrow 2)(d^{(k)}(Z))$

for k=J-1,J-2,...,M and all $n\in \mathbb {Z}$. In the Z-transform notation:

• The upsampling operator $(\uparrow 2)$ creates zero-filled holes inside a given sequence. That is, every second element of the resulting sequence is an element of the given sequence, every other second element is zero or $(\uparrow 2)(c(Z)):=\sum _{n\in \mathbb {Z} }c_{n}Z^{2n}$. This linear operator is, in the Hilbert space $\ell ^{2}(\mathbb {Z} ,\mathbb {R} )$, the adjoint to the downsampling operator $(\downarrow 2)$.