Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis. (English) Zbl 1085.65128

Zou, Jing; Gilbert, Anna; Strauss, Martin; Daubechies, Ingrid

J. Comput. Phys. 211, No. 2, 572-595 (2006).

This excellent paper greatly improves the previous randomized algorithm for sparse Fourier analysis proposed by A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan and 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.

Reviewer: Qiao Wang (Nanjing)

MSC:

65T50	Numerical methods for discrete and fast Fourier transforms
65T40	Numerical methods for trigonometric approximation and interpolation
68W20	Randomized algorithms
42A10	Trigonometric approximation

Keywords:

sparse Fourier representation; Fast Fourier transform; sublinear algorithm; randomized algorithm; numerical examples; complexity

Software:

FFTW

References:

[1]	Bensoussan, A.; Lions, P.L.; Papanicolaou, G., Asymptotic analysis for periodic structures, (1978), North-Holland Publ. Co. The Netherlands · Zbl 0411.60078
[2]	Frigo, M.; Johnson, S.G., The design and implementation of FFTW3, Proceedings of the IEEE, 93, 2, 216-231, (2005), Special Issue on Program Generation, Optimization, and Platform Adaptation
[3]	A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002. · Zbl 1192.94078
[4]	A.C. Gilbert, S. Muthukrishnan, M. Strauss, Improved Time Bounds for Near-Optimal Sparse Fourier Representation, in: Wavelets XI Conference in the SPIE Symposium on Optics and Photonics, San Diego, California, USA (to appear).
[5]	Mansour, Y., Randomized interpolation and approximation of sparse polynomials, SIAM journal on computing, 24, 2, (1995) · Zbl 0826.65005
[6]	Mansour, Y.; Sahar, S., Implementation issues in the Fourier transform algorithm, Nerual information processing systems, 260-265, (1995), [Machine Learning Journal 40 (1) 2000 5-33]
[7]	O. Runborg, Private communication, 2002.
[8]	Weaver, H.J., Applications of discrete and continuous Fourier analysis, (1983), Wiley · Zbl 0588.42002
[9]	J. Zou, I. Daubechies, O. Runborg, A Sublinear Spectral Method for Multiscale Problems (in press). · Zbl 1152.65099
[10]	J. Zou, Sublinear Algorithms for the Fourier Transform of Signals with very few Fourier modes: theory, implementations and applications, Ph.D. Thesis, Princeton University, July 2005.