Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices

Let $A$ be an $N\times N$ Fourier matrix over ${\mathbb{F}}_p^{\log N\mathrm{/}\log p}$ for some prime $p$. We improve upon known lower bounds for the number of rows of $A$ that must be sampled so that the resulting matrix $M$ satisfies the restricted isometry property for $k$-sparse vectors. This property states that $\mathrm{\parallel }Mv{\mathrm{\parallel }}_2^2$ is approximately $\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$ for all $k$-sparse vectors $v$. In particular, if $k=\mathrm{\Omega }({\log }^{2}N)$, we show that $\mathrm{\Omega }(k\log k\log N\mathrm{/}\log p)$ rows must be sampled to satisfy the restricted isometry property with constant probability.