Inverse Fast Walsh-Hadamard Transform

Let ${\mathbf{H}}_n$ be a $2^n\times 2^n$ matrix satisfying

$${\mathbf{H}}_0=\left(\begin{array}{c}1\end{array}\right)\wedge \forall n\in \mathbb{N},{\mathbf{H}}_{n+1}=\left(\begin{array}{cc}{\mathbf{H}}_n& {\mathbf{H}}_n\\ {\mathbf{H}}_n& -{\mathbf{H}}_n\end{array}\right)$$

The Inverse Fast Walsh-Hadamard Transform is an algorithm that finds a vector $\mathbf{x}$ such that ${\mathbf{H}}_n\mathbf{x}=\mathbf{y}$ for a vector

$$\mathbf{y}=\left(\begin{array}{c}{y}_0\\ y_1\\ ⋮\\ y_{2^n-1}\end{array}\right)$$

in $\mathcal{O}(n{2}^n)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

$$\forall n\in \mathbb{N},{\mathbf{H}}_n^{-1}=\frac{1}{2^n}{\mathbf{H}}_n$$

Proof

If each $n$ in ${\mathbb{Z}}_{+}$, if ${\mathbf{H}}_{n-1}^2=2^{n-1}{\mathbf{I}}_{n-1}$,

$$\begin{array}{rl}{\mathbf{H}}_n^2& ={\left(\begin{array}{cc}{\mathbf{H}}_{n-1}& {\mathbf{H}}_{n-1}\\ {\mathbf{H}}_{n-1}& -{\mathbf{H}}_{n-1}\end{array}\right)}^2\\ & =\left(\begin{array}{cc}2{\mathbf{H}}_{n-1}^2& 0_{n-1}\\ 0_{n-1}& 2{\mathbf{H}}_{n-1}^2\end{array}\right)\\ & =\left(\begin{array}{cc}{2}^n{\mathbf{I}}_{n-1}& 0_{n-1}\\ 0_{n-1}& 2^n{\mathbf{I}}_{n-1}\end{array}\right)\\ & =2^n{\mathbf{I}}_n\end{array}$$

By induction, it follows that

$$\forall n\in \mathbb{N},{\mathbf{H}}_n^2=2^n{\mathbf{I}}_n$$

Lemma

$$\mathbf{x}=\frac{1}{2^n}{\mathbf{H}}_n\mathbf{y}$$

is a vector such that ${\mathbf{H}}_n\mathbf{x}=\mathbf{y}$.

Proof

$$\begin{array}{rl}{\mathbf{H}}_n\mathbf{x}& ={\mathbf{H}}_n\left(\frac{1}{2^n}{\mathbf{H}}_n\right)\mathbf{y}\\ & ={\mathbf{H}}_n{\mathbf{H}}_n^{-1}\mathbf{y}\\ & =\mathbf{y}\end{array}$$

0. Apply the Fast Walsh-Hadamard Transform to find ${\mathbf{H}}_n\mathbf{y}$.
1. Apply the lemma to find $\mathbf{x}$.

This algorithm solves the problem in $\mathcal{O}(n{2}^n)$ time and $\mathcal{O}(1)$ space.

void ifwht(int n, std::vector<int> &a) {
	fwht(n, a);
	for (int i = 0; i < 1 << n; i++) {
		a[i] >>= n;
	}
}