The Restricted Isometry Property of Subsampled Fourier Matrices

A matrix $A\in {\mathbb{C}}^{q\times N}$ satisfies the restricted isometry property of order $k$ with constant $\epsilon$ if it preserves the ${\mathrm{\ell }}_2$ norm of all $k$-sparse vectors up to a factor of $1\pm \epsilon$. We prove that a matrix $A$ obtained by randomly sampling $q = O(k \cdot \log^2 k \cdot \log N)$rowsfroman$N \times N$ Fourier matrix satisfies the restricted isometry property of order $k$ with a fixed $\epsilon$ with high probability. This improves on Rudelson and Vershynin (Comm. Pure Appl. Math., 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).