Hadamard Transform: Unveiling the Power of Hadamard Transform in Computer Vision

By Fouad Sabry

What is Hadamard Transform

The Hadamard transform is an example of a generalized class of Fourier transforms. It performs an orthogonal, symmetric, involutive, linear operation on 2m real numbers.

How you will benefit

(I) Insights, and validations about the following topics:

Chapter 1: Hadamard transform

Chapter 2: Discrete Fourier transform

Chapter 3: Fast Walsh-Hadamard transform

Chapter 4: Quantum Fourier transform

Chapter 5: Bracket notation

Chapter 6: Pauli matrices

Chapter 7: Quantum logic gate

Chapter 8: Controlled NOT gate

Chapter 9: Generalizations of Pauli matrices

Chapter 10: Spherical basis

(II) Answering the public top questions about hadamard transform.

(III) Real world examples for the usage of hadamard transform in many fields.

Who this book is for

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of Hadamard Transform.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Apr 28, 2024

Book preview

Chapter 1: Hadamard transform

The Hadamard transform (also referred to as the Walsh-Hadamard transform), Hadamard transform, Rademacher-Walsh transform, and Walsh transform, Walsh transform, or Walsh-Fourier transform) is a type of Fourier transform that belongs to a broader category.

It solves an orthogonal equation, symmetric, involutive, linear operation on 2m real numbers (or complex, , very complicated numbers, even though Hadamard matrices are entirely non-imaginary).

It is possible to think of the Hadamard transform as being constructed from discrete Fourier transforms of size 2. (DFTs), and is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2.

It takes any input vector and decomposes it into a superposition of Walsh functions.

The transform is named for the French mathematician Jacques Hadamard (French: [adamaʁ]), Mathematician of German and American ancestry Hans Rademacher, Joseph L. Weisstein Jr. of the United States.

Walsh.

The Hadamard transform Hm is a 2m × 2m matrix, Hadamard's matrix (scaled by a normalization factor), that transforms 2m real numbers xn into 2m real numbers Xk.

There are two different approaches to define the Hadamard transform, alternatively, by writing n and k in binary (base-2) form.

Recursively, we define the 1 × 1 Hadamard transform H0 by the identity H0 = 1, and then define Hm for m > 0 by:

{\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}

where the 1/√

2

is a normalization that is sometimes omitted.

For m > 1, we can also define Hm by:

{\displaystyle H_{m}=H_{1}\otimes H_{m-1}}

where \otimes represents the Kronecker product.

Thus, Besides this standardization parameter, Hadamard matrices are all ones and zeros.

Alternatively, the Hadamard matrix can be defined by its (k, n)-th element, as shown in the following

{\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}

where the kj and nj are the bit elements (0 or 1) of k and n, respectively.

Take heed, that is for the item in the upper left, we define: k=n=0 .

Here, though,, we have:

{\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}

This is exactly the multidimensional {\textstyle 2\times 2\times \cdots \times 2\times 2} DFT, conformed to a single standard, if the inputs and outputs are regarded as multidimensional arrays indexed by the nj and kj, respectively.

Here are some specific Hadamard matrix examples.

{\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{array}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}

where i\cdot j is the bitwise dot product of the binary representations of the numbers i and j.

For example, if {\textstyle n\;\geq \;2} , then

{\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}

confirming the preceding (ignoring the overall constant).

Keep in mind that the first row, first column element of the matrix is denoted by {\textstyle (H_{n})_{0,0}} .

H1 is precisely the size-2 DFT.

The additive group of two elements, Z/, can be thought of as undergoing a Fourier transformation (2).

Hadamard matrices have Walsh functions in their rows.

Let H = Hm,n] be a matrix H satisfying the preceding definition.

{\displaystyle H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}

The Walsh transform produces a matrix with only the entries 1 and 1. Due to the nature of 1 and 1, neither of which are complex numbers, a complex number calculation is unnecessary.

Irrational multiplication is required for the DFT but not for the Hadamard transform. In fact, sign changes are sufficient, therefore rational multiplication is unnecessary.

All entries in the first row (and column) of the Walsh transform matrix are 1.

{\displaystyle H[m,n]=\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{array}}\right)}

Discrete Fourier transform：

{\displaystyle e^{-j2\pi mn/N}}

When m is equal to zeros (the average of the first row), the discrete Fourier transform (DFT) also yields 1. Despite its differences from the first row, the second row reveals an important feature of the matrix: the signal in the initial raw matrix is low-frequency, but this changes as the rows progress.

If we use the zero crossing calculation:

First row = 0 zero crossing

Second row = 1 zero crossing

Third row = 2 zero crossings

⋮

Eight row = 7 zero crossings

The Hadamard transform is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2.

Another approach is to view the Hadamard transform as a Fourier transform on the Boolean group {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} .

Applying the Fourier transform to groups that are finite (abelian), the Fourier transform of a function {\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } is the function {\widehat {f}} defined by

{\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}

where \chi is a character of (\Z/2\Z)^n .

Each character has the form {\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}} for some {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} , where a bit string is multiplied by itself using the boolean dot product, so we can identify the input to {\widehat {f}} with {\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}} (Pontryagin duality) and define {\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} } by

{\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}

This is the Hadamard transform of f , considering the input to f and {\widehat {f}} as boolean strings.

In terms of the above formulation where the Hadamard transform multiplies a vector of 2^{n} complex numbers v on the left by the Hadamard matrix H_{n} the equivalence is seen by taking f to take as input the bit string corresponding to the index of an element of v , and having f output the corresponding element of v .

Compare this to the usual discrete Fourier transform which when applied to a vector v of 2^{n} complex numbers instead uses characters of the cyclic group {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Whereas the classical field, the Hadamard transform can be computed in n\log n operations ( n=2^{m} ), by use of a speedy Hadamard transform method.

Quantum mechanics, the Hadamard transform can be computed in O(1) time, since it is a parallelizable quantum logic gate.

Quantum computing relies heavily on the Hadamard transform.

The 2 × 2 Hadamard transforms H_{1} is the quantum logic gate known as the Hadamard gate, and the application of a Hadamard gate to each qubit of an n-qubit register in parallel is equivalent to the Hadamard transform H_{n} .

Computing on a quantum level, The Hadamard gate performs a rotation of a single qubit, mapping the qubit-basis states |0\rangle and |1\rangle to two superposition states with equal weight of the computational basis states |0\rangle and |1\rangle .

Phases are typically selected to ensure

{\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}

in the notation of Dirac. That's the matrix that does the transforming, by the way.

{\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}

in the |0\rangle ,|1\rangle basis, equivalent to the computational foundation.

The states {\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}} and {\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}} are known as {\displaystyle \left|{\boldsymbol {+}}\right\rangle } and {\displaystyle \left|{\boldsymbol {-}}\right\rangle } respectively, Together, they provide quantum computing's polar foundation.

{\displaystyle {\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|1\rangle \end{aligned}}}

When applied to a 0 or 1 qubit, the Hadamard gate creates a quantum state that has an equal chance of being either 0 or 1. (as seen in the first two operations). In the traditional probabilistic paradigm of computation, this is equivalent to tossing a fair coin. The final state is always the same as the initial state if the Hadamard gate is applied twice in succession (as is effectively done in the last two procedures).

Due to the tensor product nature of the Hadamard transform, computing the quantum Hadamard transform is as easy as applying a Hadamard gate to each qubit separately. According to this straightforward conclusion, in contrast to the n log n operations needed in the classical situation, the quantum Hadamard transform only needs log n operations.

The Hadamard transform is the cornerstone of many quantum algorithms, since it maps m qubits initialized with |0\rangle to a superposition of all 2m orthogonal states in the |0\rangle ,|1\rangle basis with equal weight.

For example, The Deutsch-Jozsa algorithm relies on this information, Simon's algorithm, algorithimum Bernstein-Vazirani, Moreover, Grover's algorithm.

To begin with, Shor's approach employs a Hadamard transform, not to mention QFT (quantum Fourier transform), and are, respectively, Fourier transformations on finite groups and Fourier series; the first on {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} and the second on {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } .

Phylogenetic trees can be inferred from molecular data using the Hadamard transform.

The mechanics of the phylogenetic Hadamard transform involve the calculation of a vector {\displaystyle \gamma (T)} that provides information about the topology and branch lengths for tree T using the site pattern vector or matrix {\displaystyle s(T)} .

{\displaystyle \gamma (T)=H^{-1}(\ln(Hs(T)))}

where H is the Hadamard matrix of the appropriate size.

The complexity of this problem can be reduced by writing it as a series of three equations:

{\displaystyle {\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}}

Because this equation is invertible, we can use it to find the vector or matrix that represents the typical configuration of a given site::

{\displaystyle s(T)=H^{-1}(\exp(H\gamma (T)))}

By storing the nucleotides as binary characters, we can apply the Cavender-Farris-Neyman (CFN) two-state substitution model for