3
$\begingroup$

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

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

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Feb 5, 2012 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
    Commented Feb 5, 2012 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.