Nearly Optimal Sparse Fourier Transform

Abstract

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.

28 pages, appearing at STOC 2012

Cited by in corpus (18)

• SCARLET: Source separation in multi-band images by Constrained Matrix Factorization
• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
• Simulating Quantum Circuits with Sparse Output Distributions
• Computing a k-sparse n-length Discrete Fourier Transform using at most 4k samples and O(k log k) complexity
• Agile Millimeter Wave Networks with Provable Guarantees
• A robust sub-linear time R-FFAST algorithm for computing a sparse DFT
• A Multiscale Sub-linear Time Fourier Algorithm for Noisy Data
• High-Dimensional Sparse Fourier Algorithms
• Functional Gaussian Process Model for Bayesian Nonparametric Analysis
• An Efficient High-Dimensional Sparse Fourier Transform
• Faster Sparse Multivariate Polynomial Interpolation of Straight-Line Programs
• Sparse Multipath Channel Estimation and Decoding for Broadband Vector OFDM Systems
• Rapidly Computing Sparse Legendre Expansions via Sparse Fourier Transforms
• Fast Haar Transforms for Graph Neural Networks
• A hybrid Fourier-Prony method
• Summable Reparameterizations of Wasserstein Critics in the One-Dimensional Setting
• Robust Sparse Fourier Transform Based on The Fourier Projection-Slice Theorem
• The Polynomial Transform