Ex. 5.19

Show that the Haar wavelet transform of a signal of length \(N=2^J\) can be computed in \(O(N)\) computations.

Soln. 5.19

We refer to Section 2.1 in Wavelet Methods in Statistics with R for readers interested in the pyramidal technique for Haar wavelet transform. Here we give a high level idea on why the time complexity is \(O(N)\).

Given a discrete sequence of data \(y=(y_1,y_2,...,y_N)\), without loss of generality, we assume that \(N=2^J\) for some integer \(J\ge 0\), the pyramidal technique consists of \(J\) steps, in each step, we calculate

\[\begin{eqnarray} d_{j, k} = \frac{1}{\sqrt {2}} ( c_{j+1, 2k} - c_{j+1, 2k-1} )\non\\ c_{j, k} = \frac{1}{\sqrt {2}} ( c_{j+1, 2k} + c_{j+1, 2k-1} )\non \end{eqnarray}\]

for \(j=J-1,...,0\) and \(k=1,...,2^{j}\). Let \(c_{J, k} = y_k\) for initialization. At \(j\)-th step, the time complexity is \(2 * 2^j=2^{j+1}\), therefore the total time complexity is

\[\begin{equation} \sum_{j=0}^{J-1}2^{j+1} = 2(2^J-1) = 2(N-1).\non \end{equation}\]

Thus the complexity is \(O(N)\).