Wavelet Matrix

A Matrix composed of Haar Functions which is used in the Wavelet Transform. The fourth-order wavelet matrix is given by

$\displaystyle {W}_4$	$\textstyle =$	$\displaystyle \left[\begin{array}{cccc}1 & 1 & 1 & 0\\ 1 & 1 & -1 & 0\\ 1 & -1 & 0 & 1\\ 1 & -1 & 0 & -1\end{array}\right]$
	$\textstyle =$	$\displaystyle \left[\begin{array}{cccc}1 & 1 & & \\ 1 & -1 & & \\ & & 1 & 1\\... ...array}{cccc}1 & 1 & & \\ 1 & -1 & & \\ & & 1 & \\ & & & 1\end{array}\right].$

A wavelet matrix can be computed in ${\mathcal O}(n)$ steps, compared to ${\mathcal O}(n\lg n)$ for the Fourier Matrix, where $\lg x=\log_2 x$ is the base-2 Logarithm.

See also Fourier Matrix, Wavelet, Wavelet Transform