Everything up to this point has been a review of Hilbert space theory. Note that the main value of this theory is that operators may be analysed in terms of their associated eigenspaces, i.e. in terms of known basis functions.
The Haar basis is an orthogonal basis which has been known since 1910 [Haar]. It is also the earliest known example of a wavelet basis, and perhaps one of the simplest. For these reasons we will use it in outlining the basics of wavelet analysis.
In Hilbert space analysis, one finds the union of eigenspaces of a linear operator and determines the basis of that space. The operator itself is chosen to reflect some aspect of the problem domain. For example, one might choose a 2nd-order ODE with constant coefficients to describe some sort of simple harmonic oscillator. The basis of the eigenspace is readily shown to be made of sine and cosine functions with definite periods.
Wavelet analysis provides other means to generate a basis suited to the problem domain. For example, the Haar basis may be generated from a so-called ``mother function'' in formulaic fashion. This strategy is used in a general fashion to create wavelet families. One prescription used to generate a wavelet family from a suitable function is
For some very special choices of and the constitute an orthonormal basis for . In particular, for there do exist such that the
form an orthonormal basis of . Indeed, all but the last chapter of [Daubechies] is concerned with bases arising from the choice . This is the generating function we will use.
The Haar basis can be generated by these means from the Haar function
This function is shown in Figure 1.
Figure 1: The Haar function .
To establish that the Haar family does indeed constitute an orthonormal basis we must show that
First we check orthogonality. The support of is readily seen to be , which leads immediately to the conclusion that when . Stated another way, Haar wavelets of the same scale m do not overlap unless they share the same index of translation n. This leads to the integral
. Thus we have .
Checking orthogonality in the case of differing scale is a bit harder. Given and the supports will be and . The situation is illustrated in Figure 2, for Haar wavelets and (four wavelets of scale m=0). It is easy to check that if then the support of lies wholly within a region where is constant. Thus the integrand cancels itself in the integration. By switching the wavelets we can show the same thing for .
Figure 2: The Haar wavelets (solid) and (dashed). Note that the height of such a wavelet goes as the inverse square root of its width.
Combining this last with the previous result concerning wavelet scale, we finally have that . Thus the are an orthonormal family of compactly supported wavelets.
Now we would like to show that it is possible to expand any in a finite number of terms of so that
for arbitrarily small . In other words, we are looking for the partial sum to converge in the mean square metric. The formal proof of this is a delightful exercise in the notation of intervals and is presented very clearly in the book by [Daubechies]. We summarize the proof briefly.
Because any function is Lebesgue-integrable, we know that f can be arbitrarily well approximated by a function with compact support which is piecewise constant on intervals (for sufficiently large support and j). We may choose two adjacent intervals that exactly overlap the interval of some Haar wavelet and represent their difference by a constant . This process is repeated until the support of f is covered by wavelets of scale -j+1. Then we go back to choose constants and cover the support of f with wavelets of scale -j+2.
This process is repeated until the support of the wavelet engulfs the support of f, at which point successive wavelets begin to represent the (diminishing) total error of the partial sum. This can be extended indefinitely, until the given error threshold is reached. Thus f can be arbitrarily well approximated by a partial series expansion of Haar wavelets.