Sample-Optimal Fourier Sampling in Any Constant Dimension -- Part I

Piotr Indyk, Michael Kapralov

We give an algorithm for ${\ell }_2/{\ell }_2$ sparse recovery from Fourier measurements using $O(k\log N)$ samples, matching the lower bound of \cite{DIPW} for non-adaptive algorithms u…