Hadamard transform

The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal, symmetric, involutive, linear operation on a tuple of 2m numbers. The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2. It decomposes an arbitrary input vector into a superposition of Walsh functions. The transform is named for the French mathematician Jacques Hadamard (French: [adamaʁ]), the German-American mathematician Hans Rademacher, and the American mathematician Joseph L. Walsh.

Definition The Hadamard transform Hm is a 2m × 2m matrix, the Hadamard matrix (scaled by a normalization factor), that transforms 2m real numbers xn into 2m real numbers Xk. The Hadamard transform can be defined in two ways: recursively, or by using the binary (base-2) representation of the indices n and k. Recursively, we define the 1 × 1 Hadamard transform H0 by the identity H0 = 1, and then define Hm for m > 0 by:

H m = 1 2 m / 2 ( H m − 1 H m − 1 H m − 1 − H m − 1 ) {\displaystyle H_{m}={\frac {1}{2^{m/2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}

where the division by 2m/2 is a normalization that is sometimes omitted. For m > 1, we can also define Hm by:

H m = H 1 ⊗ H m − 1 {\displaystyle H_{m}=H_{1}\otimes H_{m-1}}

where ⊗ {\displaystyle \otimes } represents the Kronecker product. Thus, other than this normalization factor, the Hadamard matrices are made up entirely of 1 and −1. Equivalently, we can define the Hadamard matrix by its (k, n)-th entry by writing

… excerpt ends here. Continue reading the full article.