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

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

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.

  • $\begingroup$ I believe that these papers deal with a sparse approximation of a general function, while I'm interested in (efficient) exact computation of a sparse function. $\endgroup$ – user887 Feb 5 '12 at 12:20
  • $\begingroup$ 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. $\endgroup$ – Martin Schwarz Feb 5 '12 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy