(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless

Abstract

In this paper, we consider the extensively studied problem of computing a $k$-sparse approximation to the $d$-dimensional Fourier transform of a length $n$ signal. Our algorithm uses $O(k\log k\log n)$ samples, is dimension-free, operates for any universe size, and achieves the strongest ${\ell }_{\infty }/{\ell }_2$ guarantee, while running in a time comparable to the Fast Fourier Transform. In contrast to previous algorithms which proceed either via the Restricted Isometry Property or via filter functions, our approach offers a fresh perspective to the sparse Fourier Transform problem.

References in corpus (1)

• Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices

Cited by in corpus (2)

• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments