Nearly optimal sparse fourier transform

By Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price. Symposium on the Theory of Computing, 2012

351 citations recorded by the source corpus.

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: An O(k log n)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and An O(k log n log(n/k))-time randomized algorithm for general input signals. Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k=o(n). They are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = nΩ(1). We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least Ω(k log (n/k) / log log n) signal samples, even if it is allowed to perform adaptive sampling.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/7c69c424784595ea604014971d639ca40b805582

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Numerical Analysis

Citations in the corpus

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.”
Sparse Recovery for Orthogonal Polynomial Transforms (2019, methodology): “In this case, the matrix F is taken to be the Discrete Fourier Transform (DFT) and a long line of work has produced near-optimal results: algorithms with running time O(k polylog(N)) and sample complexity O(k logN) [15, 18, 19].”
Superfast Fourier Transform Using QTT Approximation (2012, methodology): “The nearly optimal Sparse Fourier transform algorithm was recently proposed by MIT group [18, 19].”
Caraoke: An E-Toll Transponder Network for Smart Cities (2015, methodology): “For such sparse signals, one can compute the Fourier transform in sublinear time [32, 31].”