Question

The Hadamard matrices${\mathit{H}}_{\mathbf{0}}\mathbf{,}{\mathit{H}}_{\mathbf{1}}\mathbf{,}{\mathit{H}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }$ are defined as follows:

• • ${\mathit{H}}_{\mathbf{0}}$ is the $\mathbf{1}\mathbf{\times }\mathbf{1}\mathbf{}\mathit{m}\mathit{a}\mathit{t}\mathit{r}\mathit{i}\mathit{x}\mathbf{}\mathbf{\left[}\mathbf{1}\mathbf{\right]}\mathbf{}$
• For $\mathit{k}\mathbf{>}\mathbf{0}\mathbf{,}\mathbf{}{\mathit{H}}_{\mathbf{k}}\mathit{i}\mathit{s}\mathbf{}\mathit{t}\mathit{h}\mathit{e}\mathbf{}{\mathbf{2}}^{\mathbf{k}}\mathbf{\times }{\mathbf{2}}^{\mathbf{k}}$ matrix

localid="1658916810283" ${\mathit{H}}_{\mathbf{k}}\mathbf{=}\mathbf{\left[}\frac{{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{|}{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}}{{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{|}\mathbf{-}{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}}\mathbf{\right]}$

Show that if $\mathit{\upsilon }$ is a column vector of lengthlocalid="1658916598888" $\mathit{n}\mathbf{=}{\mathbf{2}}^{\mathbf{k}}$, then the matrix-vector product localid="1658916618774" ${\mathit{H}}_{\mathbf{k}}\mathit{v}$can be calculated using localid="1658916637767" $\mathit{O}\mathbf{(}\mathit{n}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathit{n}\mathbf{}\mathbf{)}\mathbf{}$ operations. Assume that all the numbers involved are small enough that basic arithmetic operations like addition and multiplication take unit time.

Short answer

If is a column vector of length $n=2^{\mathrm{k}}$, then the matrix-vector product $H_{\mathrm{k}}v$ is calculated using role="math" localid="1658916653689" $O(nlogn)$operations.

Step-by-step solution

Explain Hadamard matrices.

The Hadamard matrix ${\mathit{H}}_{\mathbf{0}}$ is the matrix. Consider the ${\mathbf{2}}^{\mathbf{k}}\mathbf{\times }{\mathbf{2}}^{\mathbf{k}}$ matrix is defined as${\mathit{H}}_{\mathbf{k}}\mathbf{.}\mathbf{,}\mathbf{}\mathit{f}\mathit{o}\mathit{r}\mathbf{}\mathit{k}\mathbf{>}\mathbf{0}$

. The Hadamard matrices should be defined with the mentioned properties as follows,

localid="1658916992923" ${\mathit{H}}_{\mathbf{k}}\mathbf{=}\mathbf{\left[}\frac{{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{|}{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}}{{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{|}\mathbf{-}{\mathbf{H}}_{\mathbf{k}\mathbf{-}\mathbf{1}}}\mathbf{\right]}$

Show that the matrix-vector product   can be calculated using   operations.

Consider the Hadamard matrices $H_0,H_1,H_2,\dots$defined as follows,

$H_{\mathrm{k}}=\left[\frac{{\mathrm{H}}_{\mathrm{k}-1}|{\mathrm{H}}_{\mathrm{k}-1}}{{\mathrm{H}}_{\mathrm{k}-1}|-{\mathrm{H}}_{\mathrm{k}-1}}\right]$

Consider that If is a column vector of length $n=2^k,$, then the matrix-vector product $H_{k}v$ is calculated as follows,

$$\begin{gathered} H_{k}V=\left[\begin{array}{cc}{H}_{k-1}& H_{k-1}\\ H_{k-1}& -H_{k-1}\end{array}\right]\left[\begin{array}{c}{V}_u\\ V_d\end{array}\right] \\ =\left[\begin{array}{c}{H}_{k-1}\left(v_u+V_d\right)\\ H_{k-1}\left(v_u+V_d\right)\end{array}\right] \end{gathered}$$

The above calculation has the arithmetic operations that takes unit time. Then the complexity of operations can be calculated as follows,

$$\begin{gathered} T\left(n\right)=2T\left(\frac{n}{2}\right)+O\left(n\right) \\ =O\left(n\log n\right) \end{gathered}$$

Therefore, the matrix-vector product $H_{k}v$ is calculated using$O\left(n\log n\right)$operations.