Nearly Optimal Sparse Walsh-Fourier Tranform
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.