<p>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.</p>

<p>Example:</p>

<p>d = 4.</p>

<p>WHT H is</p>

<pre><code>++++
+-+-
++--
+--+
</code></pre>

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

<pre><code>++
++
+-
+-
</code></pre>

<p>Row blocks are</p>

<pre><code>++
++
</code></pre>

<p>and</p>

<pre><code>--
--
</code></pre>

<p>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:</p>

<pre><code>++
+-
</code></pre>

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

<pre><code>++
+-
</code></pre>

CC BY-SA 2.5
2010-10-03T20:26:24.170Z
2010-10-03T21:55:13.803Z
2010-10-03T21:55:13.803Z
Martin Strauss
<p>The <a href="http://en.wikipedia.org/wiki/Hadamard_transform">Walsh-Hadamard transform (WHT)</a> 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. </p>

<blockquote>
  <p>Suppose the input vector is <em>sparse</em>:
  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)$
  ?</p>
</blockquote>

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

CC BY-SA 2.5
2010-09-22T14:41:16.750Z
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
CC BY-SA 2.5
2010-09-22T14:55:05.473Z
Do you know what the answer is for the same question for the Fourier transform?
Robin Kothari
CC BY-SA 2.5
2010-09-22T19:45:07.050Z
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
CC BY-SA 2.5
2010-09-23T05:24:50.850Z
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
<ds.algorithms><linear-algebra>
Sparse Walsh-Hadamard Transform
Suresh Venkat
# Sparse Walsh-Hadamard Transform

(Asked by: username_0 on 2010-09-22)

The [Walsh-Hadamard transform (WHT)](http://en.wikipedia.org/wiki/Hadamard_transform) 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$.

**Tags:** ds.algorithms, linear-algebra
> **Comments:**
> **username_1**: 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.  
> **username_2**: Do you know what the answer is for the same question for the Fourier transform?  
> **username_0**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_3 on 2010-10-03. Score: 7 | Accepted answer

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:
++
+-


---

