4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is one called the average part and the other called the difference part? Thanks. $\endgroup$ – man and laptop Jul 31 '15 at 14:43
  • $\begingroup$ By the way, I may award a bounty for this answer. Or revive this question by putting a bounty on it. $\endgroup$ – man and laptop Jul 31 '15 at 14:56
  • $\begingroup$ The distinction comes from the choice of angles. The condition is that constant signals (linear, quadratic,...) transfer completely to the average part. $\endgroup$ – LutzL Aug 2 '15 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.