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