×

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

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.

MSC:

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

Software:

FFTW
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bensoussan, A.; Lions, P. L.; Papanicolaou, G., Asymptotic Analysis for Periodic Structures (1978), North-Holland Publ. Co.: 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.; 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).; 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.; 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).; 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.; 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.