Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time

We consider the problem of computing a $k$-sparse approximation to the Fourier transform of a length $N$ signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving the ${\mathrm{\ell }}_2\mathrm{/}{\mathrm{\ell }}_2$ sparse recovery guarantees using Fourier measurements) using $O_d(k\log N\log \log N)$ samples of the signal in time domain that runs in time $O_d(k{\log }^{d+3}N)$, where $d\ge 1$ is the dimensionality of the Fourier transform. The sample complexity matches the lower bound of $\Omega(k\log (N/k))$fornon-adaptivealgorithmsdueto\text{cite}DIPWforany$k\leq N^{1-\delta}$foraconstant$\delta>0$uptoan$O(\log\log N)$ factor. Prior to our work a result with comparable sample complexity $k\log N \log^{O(1)}\log N$ and sublinear runtime was known for the Fourier transform on the line \cite{IKP}, but for any dimension $d\ge 2$ previously known techniques either suffered from a polylogarithmic factor loss in sample complexity or required $\mathrm{\Omega }(N)$ runtime.