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$.

• I am sure that you are aware of the following two easy observations, but anyway I will write them down for other readers: (1) A straightforward multiplication gives O(rd) time. It is better than O(d log d) only when r=o(log d). (2) Even if the input vector is sparse, the output is not sparse in general. This means that we cannot hope for f(r,d) to be o(d) even for r=1. – Tsuyoshi Ito Sep 22 '10 at 14:41
• Do you know what the answer is for the same question for the Fourier transform? – Robin Kothari Sep 22 '10 at 14:55
• Tsuyoshi: yes, I'm aware of (1) and that is in fact what is done for applications that need this. as for (2) that's true as well. Robin, that's a good point - I don't know about anything for the FT, and in fact that might be a good place to start digging. – Suresh Venkat Sep 22 '10 at 19:45
• It turns out I should have been digging on wikipedia. the FFT page mentions two papers that might be related to the sparse computation problem. – Suresh Venkat Sep 23 '10 at 5:24

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:

++
+-