# 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$) ?

• Have you asked the authors about this? They may have a quick answer for you. – Mahdi Cheraghchi Feb 5 '12 at 10:04
• That's a good idea. I will ask and update in case I get an interesting answer. – user887 Feb 5 '12 at 10:38

• There are sparse Fourier approximation algorithms, that guarantee to recover the signal exactly, if it is indeed $k$-sparse. E.g. [GGI+02] dl.acm.org/citation.cfm?id=509933 talks about this explicitly. – Martin Schwarz Feb 5 '12 at 13:08