Haar Transform

The Haar functions

The family of N Haar functions are defined on the interval . The shape of the specific function of a given index depends on two parameters t and :

For any value of , and are uniquely determined so that is the largest power of 2 contained in () and is the remainder . For example, when , the index with the corresponding and are shown in the table:

Now the Haar functions can be defined recursively as:
• When , the Haar function is defined as a constant

• When , the Haar function is defined by

From the definition, it can be seen that determines the amplitude and width of the non-zero part of the function, while determines the position of the non-zero part of the function.

The Haar Transform Matrix

The N Haar functions can be sampled at , where to form an by matrix for discrete Haar transform. For example, when , we have

when , we have

and when

We see that all Haar functions contains a single prototype shape composed of a square wave and its negative version, and the parameters

• specifies the magnitude and width (or scale) of the shape;
• specifies the position (or shift) of the shape.
Note that the functions of Haar trnasform can represent not only the details in the signal of different scales (corresponding to different frequencies) but also their locations in time.

The Haar transform matrix is real and orthogonal:

where is identity matrix. For example, when ,

In general, an N by N Haar matrix can be expressed in terms of its row vectors:

where is the nth row vector of the matrix. The Haar tansform of a given signal vector is

with the n-th component of being

which is the nth transform coefficient, the projection of the signal vector onto the n-th row vector of the transform matrix. The inverse transform is

i.e., the signal is expressed as a linear combination of the row vectors of .

Comparing this Haar transform matrix with all transform matrices previously discussed (e.g., Fourier transform, cosine transform, Walsh-Hadamard transform), we see an essential difference. The row vectors of all previous trnasform methods represent different frequency (or sequency) components, including zero frequency or the average or DC component (first row ), and the progressively higher frequencies (sequencies) in the subsequent rows ( ). However, the row vectors in Haar transform matrix represent progressively smaller scales (narrower width of the square waves) and their different positions. It is the capability to represent different positions as well as different scales (corresponding different frequencies) that distinguish Haar transform from the previous transforms. This capability is also the main advantage of wavelet transform over other orthogonal transforms.

A Haar Transform Example:

The Haar transform coefficients of a -point signal can be found as

The inverse transform will express the signal as the linear combination of the basis functions:

Note that coefficients and indicate not only there exist some detailed changes in the signal, but also where in the signal such changes take place (first and second halves). This kind of position information is not available in any other orthogonal transforms.