The Restricted Isometry Property of Subsampled Fourier Matrices

Abstract

A matrix $A\in {\mathbb{C}}^{q\times N}$ satisfies the restricted isometry property of order $k$ with constant $\epsilon$ if it preserves the ${\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)$ rows from an $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).

arXiv comment16 pages