Linear algebra explanation of wavelet transform

Question

Is there an easy way to explain wavelets / wavelet transform using only linear algebra?

The discrete Fourier transform is a linear operator on $\mathbb C^N$ that simply changes basis to a special basis, the "discrete Fourier basis". Each $N$th root of unity $\omega$ gives us a basis vector $v = \begin{bmatrix} 1 & \omega & \omega^2 & \cdots & \omega^{N-1} \end{bmatrix}^T$. It's immediate to check that $v$ is an eigenvector of the cyclic shift operator $S$ with eigenvalue $1/\omega = \bar{\omega}$. $S$ preserves norms $\implies S$ is unitary $\implies S$ is normal ($S^* S = S S^* = I$), so eigenvectors corresponding to distinct eigenvalues of $S$ are orthogonal. Hence, once we normalize we have an orthonormal basis of eigenvectors of $S$.

Is there some similar linear algebra explanation of wavelets?

Answer 1

Wavelet filter banks act on doubly infinite sequences. There is a block division involved, most commonly a division into blocks of 2, but the higher order wavelet transform combine values from several blocks for each block of the result.

Orthogonal filterbanks of length 4, among them the D4 wavelet transform, can be composed of two blockwise rotations. If the signal is

$(\dots,x_{-1},x_0,x_1,x_2,\dots)$,

then the first rotation acts on odd-even blocks,

$\begin{pmatrix}x'_{2n-1}\\x'_{2n}\end{pmatrix} = \begin{pmatrix}\cos\alpha&-\sin\alpha\\\sin\alpha&\cos\alpha\end{pmatrix} \begin{pmatrix}x_{2n-1}\\x_{2n}\end{pmatrix}$.

The second rotation then acts on even-odd blocks

$\begin{pmatrix}x''_{2n}\\x''_{2n+1}\end{pmatrix} = \begin{pmatrix}\cos\beta&-\sin\beta\\\sin\beta&\cos\beta\end{pmatrix} \begin{pmatrix}x'_{2n}\\x'_{2n+1}\end{pmatrix}$.

It should be evident that these operations preserve the standard scalar product on the sequence space $\ell^2(\mathbb Z)$, since it is preserved in each block.

After that, the twice rotated signal is split to form the average part

$(\dots,x''_{-2},x''_0,x''_2,\dots)$

and the difference or wavelet part

$(\dots,x''_{-1},x''_1,x''_2,\dots)$.

For D4, the angles are chosen in such a way that for locally linear signal the wavelet part is zero at those linear locations.

All orthogonal discrete wavelet transforms can be decomposed in such alternations of shifts and block rotations, for general DWT the rotations are replaced by invertible matrices.