Haar Function

Define

$$\psi(x)\equiv\cases{ 1 & $0\leq x\leq {\textstyle{1\over 2}... ... & ${\textstyle{1\over 2}}\leq x \leq 1$\cr 0 & otherwise\cr}$$ (1)

and

$$\psi_{jk}(x)\equiv\psi(2^jx-k),$$ (2)

where the Functions plotted above are

$$\psi_{00} = \psi(x)$$

$$\psi_{10} = \psi(2x)$$

$$\psi_{11} = \psi(2x-1)$$

$$\psi_{20} = \psi(4x)$$

$$\psi_{21} = \psi(4x-1)$$

$$\psi_{22} = \psi(4x-2)$$

$$\psi_{23} = \psi(4x-3).$$

Then a Function $f(x)$ can be written as a series expansion by

$$f(x)=c_0+\sum_{j=0}^\infty \sum_{k=0}^{2^j-1} c_{jk}\psi_{jk}(x).$$ (3)

The Functions $\psi_{jk}$ and $\psi$ are all Orthogonal in $[0,1]$, with

$$\int_0^1 \phi(x)\phi_{jk}(x)\,dx=0$$ (4)

$$\int_0^1 \phi_{jk}(x)\phi_{lm}(x)\,dx=0.$$ (5)

These functions can be used to define Wavelets. Let a Function be defined on $n$ intervals, with $n$ a Power of 2. Then an arbitrary function can be considered as an $n$-Vector ${\bf f}$, and the Coefficients in the expansion ${\bf b}$ can be determined by solving the Matrix equation

$${\bf f}={\hbox{\sf W}}_n {\bf b}$$ (6)

for ${\bf b}$, where ${\hbox{\sf W}}$ is the Matrix of $\psi$ basis functions. For example,

$${\hbox{\sf W}}_4 =\left[{\matrix{ 1 & \hfil 1 & \hfil 1 & \h... ...cr \hfil 1 & \hfil -1 & & \cr & & 1 & \cr & & & 1\cr}}\right].$$ (7)

The Wavelet Matrix can be computed in ${\mathcal O}(n)$ steps, compared to ${\mathcal O}(n\lg n)$ for the Fourier Matrix.

See also Wavelet, Wavelet Transform

References

Haar, A. ``Zur Theorie der orthogonalen Funktionensysteme.'' Math. Ann. 69, 331-371, 1910.

Strang, G. ``Wavelet Transforms Versus Fourier Transforms.'' Bull. Amer. Math. Soc. 28, 288-305, 1993.