15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 22 '10 at 14:41
  • 4
    $\begingroup$ Do you know what the answer is for the same question for the Fourier transform? $\endgroup$ – Robin Kothari Sep 22 '10 at 14:55
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Sep 22 '10 at 19:45
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Sep 23 '10 at 5:24
6
$\begingroup$

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:

++
+-
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.