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

Vasileios Nakos, Zhao Song, Zhengyu Wang

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 us…