Sparse Walsh-Hadamard Transform

Question

The Walsh-Hadamard transform (WHT) is a generalization of the Fourier transform, and is an orthogonal transformation on a vector of real or complex numbers of dimension $d = 2^m$. The transform is popular in quantum computing, but it's been studied recently as a kind of preconditioner for random projections of high-dimensional vectors for use in the proof of the Johnson-Lindenstrauss Lemma. Its main feature is that although it's a square $d\times d$ matrix, it can be applied to a vector in time $O(d \log d)$ (rather than $d^2$) by an FFT-like method.

Suppose the input vector is sparse: it has only a few nonzero entries (say $r \ll d$). Is there any way to compute the WHT in time $f(r,d)$ such that $f(d,d) = O(d \log d)$ and $f(r,d) = o(d \log d)$ for $r = o(d)$ ?

Note: these requirements are merely one way of formalizing the idea that I'd like something that runs faster than $d \log d$ for small $r$.

Answer 1

Index the WHT rows by an integer x, for $0 \le x \lt d$. So x has log d bits. Similarly, index the columns. The (x,y) position is $(-1)^{\langle x,y \rangle}$ where the exponent is the dot product of length log d. Assume r is a power of 2, rounding up if necessary. Break the dxr matrix into rxr blocks by letting the first log r bits vary and fixing the other log(d/r) bits in each of the d/r ways. This rxr block is a smaller WHT matrix of size r, except there may be some columns missing, repeated, or negated. In any case, preprocess the vector easily then do an rxr WHT in time r log r, then repeat d/r times for total time d log r.

Example:

d = 4.

WHT H is

++++
+-+-
++--
+--+

Arbitrary set of columns is 00 and 10 (leftmost and two over from that):

++
++
+-
+-

Row blocks are

++
++

and

--
--

In each block, there are repeated columns, missing columns and, in the second block, negated columns. Preprocess a vector $(a,b)^T$ into $(a+b,0)^T$ and multiply by 2x2 WHT:

++
+-

Then preprocess $(a,b)^T$ into $(-a-b,0)^T$ and multiply by 2x2 WHT:

++
+-