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 real numbers (or complex, or hypercomplex numbers, although the Hadamard matrices themselves are purely real).
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 . It decomposes an arbitrary input vector into a superposition of Walsh functions.
The transform is named for the French mathematician Jacques Hadamard (), the German-American mathematician Hans Rademacher, and the American mathematician Joseph L. Walsh.
Definition.
The Hadamard transform "H""m" is a 2"m" × 2"m" matrix, the Hadamard matrix (scaled by a normalization factor), that transforms 2"m" real numbers "x""n" into 2"m" real numbers "X""k". 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 "H"0 by the identity "H"0 = 1, and then define "H""m" for "m" > 0 by:
where the 1/ is a normalization that is sometimes omitted.
For "m" > 1, we can also define "H""m" by:
where formula_3 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
where the "k""j" and "n""j" are the binary digits (0 or 1) of "k" and "n", respectively. Note that for the element in the top left corner, we define: formula_5. In this case, we have:
This is exactly the multidimensional formula_7 DFT, normalized to be unitary, if the inputs and outputs are regarded as multidimensional arrays indexed by the "n""j" and "k""j", respectively.
Some examples of the Hadamard matrices follow.
where formula_9 is the bitwise dot product of the binary representations of the numbers i and j. For example, if formula_10, then formula_11, agreeing with the above (ignoring the overall constant). Note that the first row, first column element of the matrix is denoted by formula_12.
"H"1 is precisely the size-2 DFT. It can also be regarded as the Fourier transform on the two-element "additive" group of Z/(2).
The rows of the Hadamard matrices are the Walsh functions.
Relation to Fourier transform.
The Hadamard transform is in fact equivalent to a multidimensional DFT of size .
Another approach is to view the Hadamard transform as a Fourier transform on the Boolean group formula_13.
 Using the Fourier transform on finite (abelian) groups, the Fourier transform of a function formula_14 is the function formula_15 defined by
where formula_17 is a character of formula_13. Each character has the form formula_19 for some formula_20, where the multiplication is the boolean dot product on bit strings, so we can identify the input to formula_21 with formula_20 (Pontryagin duality) and define formula_23 by
This is the Hadamard transform of formula_25, considering the input to formula_25 and formula_21 as boolean strings.
In terms of the above formulation where the Hadamard transform multiplies a vector of formula_28 complex numbers formula_29 on the left by the Hadamard matrix formula_30 the equivalence is seen by taking formula_25 to take as input the bit string corresponding to the index of an element of formula_29, and having formula_25 output the corresponding element of formula_29.
Compare this to the usual Discrete Fourier transform which when applied to a vector formula_29 of formula_28 complex numbers instead uses characters of the cyclic group formula_37.
Computational complexity.
In the classical domain, the Hadamard transform can be computed in formula_38 operations (formula_39), using the fast Hadamard transform algorithm.
In the quantum domain, the Hadamard transform can be computed in formula_40 time, as it is a quantum logic gate that can be parallelized.
Quantum computing applications.
The Hadamard transform is used extensively in quantum computing. The 2 × 2 Hadamard tranform formula_41 is the quantum logic gate known as the Hadamard gate, and the application of a Hadamard gate to each qubits of an n-qubit register in parallel is equivalent to the Hadamard transform formula_30.
Hadamard gate.
In quantum computing, the Hadamard gate is a one-qubit rotation, mapping the qubit-basis states formula_43 and formula_44 to two superposition states with equal weight of the computational basis states formula_43 and formula_44. Usually the phases are chosen so that we have
The much larger number of site patterns in column 0 reflects the fact that column 0 corresponds to transition differences, which accumulate more rapidly than transversion differences in virtually all comparisons of genomic regions (and definitely accumulate more rapidly in the hemoglobin pseudogenes used for this worked example). If we consider the site pattern AAGG it would to binary pattern 0000 for the second element of the Klein group bit pair and 0011 for the first element. in this case binary pattern based on the first element first element corresponds to index 3 (so row 3 in column 0; indicated with a single asterisk in the table). The site patterns GGAA, CCTT, and TTCC would be encoded in the exact same way. The site pattern AACT would be encoded with binary pattern 0011 based on the second element and 0001 based on the first element; this yields index 1 for the first element and index 3 for the second. The index based on the second Klein group bit pair is multiplied by 8 to yield the column index (in this case it would be column 24) The cell that would include the count of AACT site patterns is indicated with two asterisks; however, the absence of a number in the example indicates that the sequence alignment include no AACT site patterns (likewise, CCAG, GGTC, and TTGA site patterns, which would be encoded in the same way, are absent). 
Other applications.
The Hadamard transform is also used in data encryption, as well as many signal processing and data compression algorithms, such as JPEG XR and MPEG-4 AVC. In video compression applications, it is usually used in the form of the sum of absolute transformed differences. It is also a crucial part of Grover's algorithm and Shor's algorithm in quantum computing. The Hadamard transform is also applied in experimental techniques such as NMR, mass spectrometry and crystallography. It is additionally used in some versions of locality-sensitive hashing, to obtain pseudo-random matrix rotations.