info prev up next book cdrom email home

Haar Function

\begin{figure}\begin{center}\BoxedEPSF{HaarFns.epsf scaled 1200}\end{center}\end{figure}

Define

\begin{displaymath}
\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}
\end{displaymath} (1)

and
\begin{displaymath}
\psi_{jk}(x)\equiv\psi(2^jx-k),
\end{displaymath} (2)

where the Functions plotted above are
$\displaystyle \psi_{00}$ $\textstyle =$ $\displaystyle \psi(x)$  
$\displaystyle \psi_{10}$ $\textstyle =$ $\displaystyle \psi(2x)$  
$\displaystyle \psi_{11}$ $\textstyle =$ $\displaystyle \psi(2x-1)$  
$\displaystyle \psi_{20}$ $\textstyle =$ $\displaystyle \psi(4x)$  
$\displaystyle \psi_{21}$ $\textstyle =$ $\displaystyle \psi(4x-1)$  
$\displaystyle \psi_{22}$ $\textstyle =$ $\displaystyle \psi(4x-2)$  
$\displaystyle \psi_{23}$ $\textstyle =$ $\displaystyle \psi(4x-3).$  

Then a Function $f(x)$ can be written as a series expansion by
\begin{displaymath}
f(x)=c_0+\sum_{j=0}^\infty \sum_{k=0}^{2^j-1} c_{jk}\psi_{jk}(x).
\end{displaymath} (3)

The Functions $\psi_{jk}$ and $\psi$ are all Orthogonal in $[0,1]$, with
\begin{displaymath}
\int_0^1 \phi(x)\phi_{jk}(x)\,dx=0
\end{displaymath} (4)


\begin{displaymath}
\int_0^1 \phi_{jk}(x)\phi_{lm}(x)\,dx=0.
\end{displaymath} (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
\begin{displaymath}
{\bf f}={\hbox{\sf W}}_n {\bf b}
\end{displaymath} (6)

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


\begin{displaymath}
{\hbox{\sf W}}_4 =\left[{\matrix{ 1 & \hfil 1 & \hfil 1 & \h...
...cr \hfil 1 & \hfil -1 & & \cr & & 1 & \cr & & & 1\cr}}\right].
\end{displaymath} (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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25