Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis (Q2572217)

This excellent paper greatly improves the previous randomized algorithm for sparse Fourier analysis proposed by \textit{A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan} and \textit{M. Strauss}, Near-optimal sparse Fourier representations via sampling, Proc. Thirty-Fourth Annual ACM Symp. on Theory of Computing, 152--161 (2002)]. Several novel ideas and techniques to speed up the algorithm, as well as rigorous and heuristic arguments for choosing parameters, are presented. The approach to higher dimensional cases is also introduced and demonstrated. Various experiments, even with different levels of noise are given in details. The time and spatial complexity are analyzed. Almost all the results given here outperform than previous results, thus a wide range of applications can be expected, based on the important progress proposed in this paper.