For every fixed constant \alpha > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform of an N-dimensional vector x \in \mathbb{R}^N in time k^{1+\alpha} (\log N)^{O(1)}. Specifically, the algorithm is given query access to x and computes a k-sparse \tilde{x} \in \mathbb{R}^N satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>