Simple and practical algorithm for sparse Fourier transform
By Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price. ACM-SIAM Symposium on Discrete Algorithms, 2012
383 citations recorded by the source corpus.
We consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coefficients of the Fourier transform of x. The problem is of key interest in several areas, including signal processing, audio/image/video compression, and learning theory. We propose a new algorithm for this problem. The algorithm leverages techniques from digital signal processing, notably Gaussian and Dolph-Chebyshev filters. Unlike the typical approach to this problem, our algorithm is not iterative. That is, instead of estimating "large" coefficients, subtracting them and recursing on the reminder, it identifies and estimates the k largest coefficients in "one shot", in a manner akin to sketching/streaming algorithms. The resulting algorithm is structurally simpler than its predecessors. As a consequence, we are able to extend considerably the range of sparsity, k, for which the algorithm is faster than FFT, both in theory and practice.
Subfields: Artificial Intelligence, Computational Mechanics
View Paper: https://www.semanticscholar.org/paper/8a23fb198c5651c44c2f51ce9967aca7d5bf6b2c
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Boris N. Khoromskij
- Jack Murtagh
- Nikhil Vyas
- Dmitry V. Savostyanov
- Sergey V. Dolgov
- Mitali Bafna
- Thomas Steinke
In Computational Mechanics
- Sergey V. Dolgov
- Dmitry V. Savostyanov
- Boris N. Khoromskij
- Jack Murtagh
- Nikhil Vyas
- Mitali Bafna
- Ivan V. Oseledets
- Christine Tobler
Citations in the corpus
- Superfast Fourier Transform Using QTT Approximation (2012, methodology): “The nearly optimal Sparse Fourier transform algorithm was recently proposed by MIT group [18, 19].”
- Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform (2018, methodology): “Variants of the Sparse Fourier Transform have been studied [HIKP12a, HIKP12b, IKP14] but that work is concerned with recovering ˆ x h ( k ) given an approximately sparse vector x , using sublinear measurements.”