# Haar wavelet transform

A definition of the Haar wavelet transform is provided below. There are many ways to define the transform. The definition here is derived from the following example decomposition of a short audio signal.

## Example level eight Haar wavelet transform of a signal

Consider the following example signal.

This example signal is the sum of two simple sine waves, one with a frequency of 5 Hz and phase of zero (i.e., the wave starts with the value zero at sample zero) and one with a frequency of 9 Hz and shifted to the right by 10 samples. The sampling frequency is 256 Hz and the graph above shows 256 samples (1 second) of the signal.

Denote the value of this signal at sample k with x(k). Let K = 256 and, for 1 second of time, k = 0, 1, …, K – 1. Compute

$$a_1(j)=\frac{x(k-1)+x(k)}{\sqrt{2}}$$ $$b_1(j)=\frac{x(k-1)-x(k)}{\sqrt{2}}$$

for j = 0, 1, …, K/2 and k = 2j + 1. The computed signal a1(j) is a moving average of x(k). It smooths out the signal x(k), removing some of the variability between two adjacent samples. It also compresses the signal x(k) in time. The signal b1(j) contains the fluctuations that the signal a1(j) removes. The following is a plot of a1(j).

Note the following.

• x(k) can be reconstructed from the signals a1(j) and b1(j)

$$x(k-1)=\frac{a_1(j)+b_1(j)}{\sqrt{2}}$$ $$x(k)=\frac{a_1(j)-b_1(j)}{\sqrt{2}}$$

• a1(j) and b1(j) preserve the energy of the signal x(k) (except for precision issues related to the quantization; see Dithering), in the sense that

$$a_1(j)^2+b_1(j)^2=x(k-1)^2+x(k)^2$$

• Often, many of the values of b1(j) are relatively small. This fact is used below. In principle, according to the Nyquist-Shannon sampling theorem, a discrete signal sampled at the sampling frequency of fs represents frequencies between 0 and fs/2. Fluctuations will be larger only if the signal contains higher frequencies. Only frequencies above fs/4 with peak amplitude of 1, for example, will contain fluctuations larger than 1.

The transformation x(k) → (a1(j) | b1(j)) is the Haar wavelet transform of level 1. To compute the Haar wavelet transform of level 2, we take the Haar wavelet transform of level 1 of the signal a1(j).

• If the signal x(k) is of length K, then the signal a1 is of length K/2, and the signal a2 is of length K/4.
• The energy of a1 is preserved in a2 and b2.
• a1 can be reconstructed similarly to above from a2 and b2. Then x(k) can be reconstructed from a2, b2, and b1. The level 2 Haar wavelet transform can then be denoted by x → (a2 | b2 | b1).

The following is a plot of our example a2, which compresses the signal even further.

Since our example signal is of 256 discrete points, this process can be continued to level 8. At level 8, a8 and b8 will each consist of a single point. The signal will be compressed to one point.

## Definition of the Haar wavelet transform

Given a signal x(k) of length K = 2N, for some integer N, the level N Haar wavelet transform of x(k) is (aN | bN | bN-1 | … | b1), where

$$a_1(j)=\frac{x(k-1)+x(k)}{\sqrt{2}}$$ $$b_1(j)=\frac{x(k-1)-x(k)}{\sqrt{2}}$$

j = 0, 1, …, K/2 and k = 2j + 1, and

$$a_n(i)=\frac{a_{n-1}(j-1)+a_{n-1}(j)}{\sqrt{2}}$$ $$b_n(i)=\frac{a_{n-1}(j-1)-a_{n-1}(j)}{\sqrt{2}}$$

n = 2, 3, …, N; i = 0, 1, …, K / 2n; and j = 2i + 1.

We note that, as before,

$$x(k-1)=\frac{a_1(j)+b_1(j)}{\sqrt{2}}$$ $$x(k)=\frac{a_1(j)-b_1(j)}{\sqrt{2}}$$ $$a_{n-1}(j-1)=\frac{a_n(i)+b_n(i)}{\sqrt{2}}$$ $$a_{n-1}(j)=\frac{a_n(j)-b_n(j)}{\sqrt{2}}$$

## Haar wavelets

An alternative way to produce a similar result is to compute the inner product of the signal x(k) with the set of functions described below. To calculate aN in the definition above, which is a single number, calculate the inner product of x(k) and

$$\psi^a_N (k)=\frac{1}{2^{\frac{N-1}{2}}}$$

We use the superscript "a" to show that these functions are used to compute the "a" portion of the Haar wavelet transform. Use the following two functions to calculate aN-1, which is a vector of two values.

$$\psi^a_{N-1} (k)=\begin{cases} (-1)^m \frac{1}{2^{\frac{N-1}{2}}}, m \frac{K}{2} \le k \lt (m+1) \frac{K}{2} \\ 0, k \lt m \frac{K}{2}, k \ge (m+1) \frac{K}{2} \end{cases}, m=0,1$$

More generally, aN-n for the N – n level of the transform can be calculated with the 2n functions (n=0, 1, …, N)

$$\psi^a_{N-n} (k)=\begin{cases} (-1)^m \frac{1}{2^{\frac{N-(n+1)}{2}}}, m \frac{K}{2^n} \le k \lt (m+1) \frac{K}{2^n} \\ 0, k \lt m \frac{K}{2^n}, k \ge (m+1) \frac{K}{2^n} \end{cases}, m= 0,1,...,2^n-1$$

To understand this result, consider the following plots of ψa8, ψa7, and ψa6 in the example above

It is only slightly more cumbersome to derive similar functions to compute the values of b. For example,

$$\psi^b_{1} (k)=\begin{cases} (-1)^k \frac{1}{2^{\frac{1}{2}}}, m \frac{K}{2^{N-1}} \le k \lt (m+1) \frac{K}{2^{N-1}} \\ 0, k \lt m \frac{K}{2^{N-1}}, k \ge (m+1) \frac{K}{2^{N-1}} \end{cases}, m= 0,1,...,2^{N-1}-1$$ $$\psi^b_{2} (k)=\begin{cases} (-1)^{int(\frac{k}{2})} \frac{1}{2^{\frac{2}{2}}}, m \frac{K}{2^{N-2}} \le k \lt (m+1) \frac{K}{2^{N-2}} \\ 0, k \lt m \frac{K}{2^{N-2}}, k \ge (m+1) \frac{K}{2^{N-2}} \end{cases}, m= 0,1,...,2^{N-2}-1$$ $$...$$ $$\psi^b_{n} (k)=\begin{cases} (-1)^{int(\frac{k}{2^{n-1}})} \frac{1}{2^{\frac{n}{2}}}, m \frac{K}{2^{N-n}} \le k \lt (m+1) \frac{K}{2^{N-n}} \\ 0, k \lt m \frac{K}{2^{N-n}}, k \ge (m+1) \frac{K}{2^{N-n}} \end{cases}, m= 0,1,...,2^{N-n}-1$$

n = 1, 2, …, N. Switch n and N-n in the last formula to obtain a result that is more consistent with the definition of ψa. The plots of ψb are very similar to the plots of ψa.

These types of functions are often defined more generally (and in the case of continuous time) with

$$\psi(x)=\begin{cases} 1, 0 \le x \lt \frac{1}{2} \\ -1, \frac{1}{2} \lt x \le 1 \\ 0, x=\frac{1}{2}, x \lt 0, x \gt 1 \end{cases}$$ $$\psi_{n,m}=\psi(2^n x - m)$$

for the integers n = 0,1, … and m=0, 1, …, 2n-1. These are the Haar wavelets. ψ(x) is known as the mother wavelet. Setting the value ψ(0.5) = 0 has its disadvantages, but that is beyond the scope of this topic.

These functions are orthogonal, since

$$\int_0^1 \psi(x) \, \psi_{n,m}(x) \, dx=0, \, (n,m) \ne (0,0)$$ $$\int_0^1 \psi_{i,j}(x) \, \psi_{n,m}(x) \, dx=0, \, (n,m) \ne (i,j)$$

These functions would become orthonormal, if we define instead

$$\psi_{n,m}=2^n \, \psi(2^n\,x-m)$$

This definition is very common, although it is not immediately obvious from this definition how to use the Haar wavelets in the Haar wavelet transform.

## Using the Haar wavelet transform: data compression and noise reduction

The fact that many of the values computed with the Haar wavelet transform are small means that the transform can be used to compress the amount of data used.

Specifically, in the example above, there are 256 values that represent the Haar wavelet transform of the signal: 128 values for b1, 64 values for b2, …, 2 values for b7, one value for b8, and one value for a8. To achieve 2:1 compression, we can simply remove the smallest 128 values and assume they are zero (i.e., zero them out and transmit only the remaining "nonzero" amounts). If we are to transmit these data, we would only have to transmit 128 values instead of 256, plus several bytes that detail the position of the nonzero values in the original signal (e.g., we can use 32 bytes or 8 four-byte integers to describe whether each of the 256 values is zero or not).

If we are to reconstruct the resulting signal from the compressed Haar wavelet transform, we would get the following.

Of course, compression of only 2:1 is not impressive and one can even achieve a similar ratio with compression techniques that do not lose information. We can, however, obtain even higher compression rations, if we are willing to sacrifice some more of the precision. We can also achieve higher compression rations with more powerful wavelets than the Haar wavelet. The same method can also be used for removing low-level random noise from the signal.

### Filtered HTML

• Freelinking helps you easily create HTML links. Links take the form of [[indicator:target|Title]]. By default (no indicator): Click to view a local node.