Haar Transform

The Haar functions

The family of N Haar functions $h_k(t),\;(k=0,\cdots,N-1)$ are defined on the interval $0 \le t \le 1$. The shape of the specific function $h_k(t)$ of a given index $k$ depends on two parameters $p$t and $q$:

$$k=2^p+q-1$$

For any value of $k\ge 0$, $p$ and $q$ are uniquely determined so that $2^p$ is the largest power of 2 contained in $k$ ($2^p<k$) and $q-1$ is the remainder $q-1=k-2^p$. For example, when $N=16$, the index $k$ with the corresponding $p$ and $q$ are shown in the table:

$$\begin{tabular}{c\vert cccccccccccccccc}\hline k & 0 & 1 & 2 ... ... 3 & 4 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \hline \end{tabular}$$

Now the Haar functions can be defined recursively as:

• When $k=0$, the Haar function is defined as a constant
  
  $$h_0(t)=1/\sqrt{N}$$
  
  

• When $k>0$, the Haar function is defined by
  
  $$h_k(t)=\frac{1}{\sqrt{N}} \left\{ \begin{array}{ll} 2^{p/2} ... ...^p \le t < q/2^p \\ 0 & \mbox{otherwise} \end{array} \right.$$
  
  

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

The Haar Transform Matrix

The N Haar functions can be sampled at $t=m/N$, where $m=0,\cdots,N-1$ to form an $N$ by $N$ matrix for discrete Haar transform. For example, when $N=2$, we have

$${\bf H}_2=\frac{1}{\sqrt{2}}\left[ \begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array} \right]$$

when $N=4$, we have

$${\bf H}_4=\frac{1}{2}\left[ \begin{array}{cccc} 1 & 1 & 1 & 1... ...} & 0 & 0 \\ 0 & 0 & \sqrt{2} & -\sqrt{2} \end{array} \right]$$

and when $N=8$

$${\bf H}_8=\frac{1}{\sqrt{8}}\left[ \begin{array}{cccccccc} 1 ... ...\\ \psi_{2,1}(t) \psi_{2,2}(t) \psi_{2,3}(t) \end{array}$$

We see that all Haar functions $h_k(t),\;(k>0)$ contains a single prototype shape composed of a square wave and its negative version, and the parameters

• $p$ specifies the magnitude and width (or scale) of the shape;
• $q$ specifies the position (or shift) of the shape.

Note that the functions $h_k(t)$ 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:

$${\bf H}={\bf H}^*,\;\;\;\;\;\;{\bf H}^{-1}={\bf H}^T, \;\;\;\;\mbox{i.e.}\;\;\;\; {\bf H}^T{\bf H}={\bf I}$$

where ${\bf I}$ is identity matrix. For example, when $N=4$,

$${\bf H}_4^{-1}{\bf H}_4={\bf H}_4^T {\bf H}_4= \frac{1}{4}\le... ...& 0 & 0 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right]$$

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

$${\bf H}=\left[ \begin{array}{c} {\bf h}^T_0 {\bf h}^T_1 ... ...;\;\; {\bf H}^{-1}={\bf H}^T=[{\bf h_0},\cdots, {\bf h_{N-1}}]$$

where ${\bf h}^T_n$ is the nth row vector of the matrix. The Haar tansform of a given signal vector ${\bf x}=[x[0],\cdots,x[N-1]]^T$ is

$${\bf X}={\bf H} {\bf x} =[{\bf h_0},\cdots, {\bf h_{N-1}}]{\bf x}$$

with the n-th component of ${\bf X}$ being

$$X[n]={\bf h}_n^T {\bf x} \;\;\;\;\;\;(n=0,\cdots,N-1)$$

which is the nth transform coefficient, the projection of the signal vector ${\bf x}$ onto the n-th row vector of the transform ${\bf H}$ matrix. The inverse transform is

$${\bf x}={\bf H}^{-1} {\bf X}={\bf H}^T {\bf X}=[{\bf h_0},\cd... ...\\ X[N-1]\end{array} \right] =\sum_{n=0}^{N-1} X[n] {\bf h}_n$$

i.e., the signal is expressed as a linear combination of the row vectors of ${\bf H}$.

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 $n=0$), and the progressively higher frequencies (sequencies) in the subsequent rows ( $n=1,\cdots,N-1$). 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 $N=4$-point signal $[x[0], x[1], x[2], x[3]]^T=[1,2,3,4]^T$ can be found as

$$\frac{1}{2}\left[ \begin{array}{cccc} 1 & 1 & 1 & 1 1 & 1... ...y}{c} 5 -2 -1/\sqrt{2} -1/\sqrt{2} \end{array} \right]$$

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

$$\frac{1}{2}\left[ \begin{array}{rrrr} 1 & 1 & \sqrt{2} & 0 \\ 1 ... ...t[ \begin{array}{c} 5 -2 -1/\sqrt{2} -1/\sqrt{2} \end{array} \right]$$

$$= \frac{1}{2}[5 \left[ \begin{array}{r} 1 1 1 1 \end{arra... ...ray} \right]] = \left[ \begin{array}{r} 1 2 3 4 \end{array} \right]$$

Note that coefficients $X[2]=-1/\sqrt{2}$ and $X[3]=-1/\sqrt{2}$ 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.