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

2019/09/24 by Nakos, Vasileios, Song, Zhao, Wang, Zhengyu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1909.11123

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 ℓ_∞/ℓ₂ 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.

Related

• Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
• Nearly Optimal Sparse Fourier Transform
• Dimension-independent Sparse Fourier Transform
• Computing a k-sparse n-length Discrete Fourier Transform using at most\n 4k samples and O(k log k) complexity
• Sample-Optimal Fourier Sampling in Any Constant Dimension -- Part I