Sparse Walsh-Hadamard Transform 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$.
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:

++
+-