Nearly Optimal Sparse Walsh-Fourier Tranform In the recent paper: Nearly Optimal Sparse Fourier Transform[Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price], the authors show an $O(k \log n)$-time algorithm for the problem of computing the discrete Fourier transform of an $n$-dimensional signal that has at most $k$ non-zero Fourier coefficients.

Is there a similar result for the Walsh-Fourier transform (or is it possible to use the same algorithm for a multidimensional DFT of size $2^n$) ?
As the quoted paper itself summarizes in its introduction, 


  The past two decades have witnessed significant advances in sublinear sparse Fourier algorithms. The first such algorithm (for the Hadamard transform)


(which is what you are looking for)


  appeared in KM91 (building on GL89). Since then, several sublinear sparse Fourier algorithms for complex inputs were discovered [Man92, GGI+02, AGS03, GMS05, Iwe10, Aka10, HIKP12].


Some of the quoted papers (e.g. Aka10) give similar results for Fourier transforms over all Abelian groups.