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

Abstract

Let $A$ be an $N\times N$ Fourier matrix over ${\mathbb{F}}_p^{\log N/\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 $\Vert Mv{\Vert }_2^2$ is approximately $\Vert v{\Vert }_2^2$ for all $k$-sparse vectors $v$. In particular, if $k=\Omega ({\log }^{2}N)$, we show that $\Omega (k\log k\log N/\log p)$ rows must be sampled to satisfy the restricted isometry property with constant probability.

Cited by in corpus (1)

• (Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless