Fast wavelet transform

Definition

Let $\varphi$ be the scaling function of an orthonormal multiresolution analysis of $L^2(\R)$ with real finite filter $(h_n)_{n \in \Z}$, so that $$\varphi(x) = \sqrt{2} \sum_{n} h_n \, \varphi(2x - n).$$ Put $g_n = (-1)^n h_{1-n}$ and let $\psi(x) = \sqrt{2}\sum_n g_n \varphi(2x - n)$ be the associated wavelet. For $j, k \in \Z$ write $\varphi_{j,k}(x) = 2^{j/2}\varphi(2^j x - k)$ and $\psi_{j,k}(x) = 2^{j/2}\psi(2^j x - k)$. For $f \in L^2(\R)$ put $a_{j,k} = \ip{f}{\varphi_{j,k}}$ and $d_{j,k} = \ip{f}{\psi_{j,k}}$.

The fast wavelet transform from level $J$ down to level $J_0 < J$ is the algorithm that takes the sequence $(a_{J,k})_k$ and, for $j = J, J-1, \dots, J_0 + 1$, computes $$a_{j-1,k} = \sum_{m} h_{m-2k} \, a_{j,m}, \qquad d_{j-1,k} = \sum_{m} g_{m-2k} \, a_{j,m}.$$ Its output is $(a_{J_0,k})_k$ together with $(d_{j,k})_k$ for $J_0 \le j < J$. The inverse fast wavelet transform computes, for $j = J_0 + 1, \dots, J$, $$a_{j,m} = \sum_{k} h_{m-2k} \, a_{j-1,k} + \sum_{k} g_{m-2k} \, d_{j-1,k}.$$