Editing Haar wavelet (section)

==Haar transform==
The '''Haar transform''' is the simplest of the [[wavelet transform]]s. This transform cross-multiplies a function against the Haar wavelet with various shifts and stretches, like the Fourier transform cross-multiplies a function against a sine wave with two phases and many stretches.<ref>[http://sepwww.stanford.edu/public/docs/sep75/ray2/paper_html/node4.html The Haar Transform<!-- Bot generated title -->]</ref>{{clarify|Is this comparing the kernels being integrated over, and decomposing exponentials into sine and cosine to treat the Fourier kernel as a space of sines, changing the parametrization accordingly? If so, we can give more specific, linkable language than "cross-multiplies", talk about inner products or projections and integrating them, and then lucidly compare that to a convolutional treatment.|date=June 2018}}

=== Introduction ===
The Haar transform is one of the oldest transform functions, proposed in 1910 by the Hungarian mathematician [[Alfréd Haar]]. It is found effective in applications such as signal and image compression in electrical and computer engineering as it provides a simple and computationally efficient approach for analysing the local aspects of a signal.

The Haar transform is derived from the Haar matrix. An example of a 4×4 Haar transformation matrix is shown below.

:<math>H_4 = \frac{1}{2}
\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ \sqrt{2} & -\sqrt{2} & 0 & 0 \\ 0 & 0 & \sqrt{2} & -\sqrt{2}\end{bmatrix}
</math>

The Haar transform can be thought of as a sampling process in which rows of the transformation matrix act as samples of finer and finer resolution.

Compare with the [[Walsh transform]], which is also 1/–1, but is non-localized.

=== Property ===
The Haar transform has the following properties

# No need for multiplications. It requires only additions and there are many elements with zero value in the Haar matrix, so the computation time is short. It is faster than [[Walsh transform]], whose matrix is composed of +1 and −1.
# Input and output length are the same. However, the length should be a power of 2, i.e. <math>N = 2^k,  k\in \mathbb{N}</math>.
# It can be used to analyse the localized feature of signals. Due to the [[orthogonal]] property of the Haar function, the frequency components of input signal can be analyzed.

=== Haar transform and Inverse Haar transform ===
The Haar transform ''y''<sub>''n''</sub> of an n-input function ''x''<sub>''n''</sub> is

: <math> y_n = H_n x_n</math>

The Haar transform matrix is real and orthogonal. Thus, the inverse Haar transform can be derived by the following equations.

: <math> H = H^*, H^{-1} = H^T, \text{ i.e. } HH^T = I </math>

: where <math>I</math> is the identity matrix. For example, when n = 4

: <math> H_4^{T}H_4 = \frac{1}{2}\begin{bmatrix} 1&1&\sqrt{2}&0 \\ 1&1&-\sqrt{2}&0 \\ 1&-1&0&\sqrt{2} \\ 1&-1&0&-\sqrt{2}\end{bmatrix}
\cdot\; \frac{1}{2}\begin{bmatrix} 1&1&1&1 \\ 1&1&-1&-1 \\ \sqrt{2}&-\sqrt{2}&0&0 \\ 0&0&\sqrt{2}&-\sqrt{2}\end{bmatrix}
= \begin{bmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \end{bmatrix}
</math>

Thus, the inverse Haar transform is

: <math> x_{n} = H^{T}y_{n}</math>

=== Example ===
The Haar transform coefficients of a n=4-point signal <math>x_{4} = [1,2,3,4]^{T}</math> can be found as

: <math> y_{4} = H_4 x_4 = 
\frac{1}{2}\begin{bmatrix} 1&1&1&1 \\ 1&1&-1&-1 \\ \sqrt{2}&-\sqrt{2}&0&0 \\ 0&0&\sqrt{2}&-\sqrt{2}\end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4\end{bmatrix}
= \begin{bmatrix} 5 \\ -2 \\ -1/\sqrt{2} \\ -1/\sqrt{2}\end{bmatrix}
</math>

The input signal can then be perfectly reconstructed by the inverse Haar transform

: <math> \hat{x_{4}} = H_{4}^{T}y_{4} = 
\frac{1}{2}\begin{bmatrix} 1&1&\sqrt{2}&0 \\ 1&1&-\sqrt{2}&0 \\ 1&-1&0&\sqrt{2} \\ 1&-1&0&-\sqrt{2}\end{bmatrix} \begin{bmatrix} 5 \\ -2 \\ -1/\sqrt{2} \\ -1/\sqrt{2}\end{bmatrix}
= \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix}
</math>