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 $\|Mv\|_2^2$ is approximately $\|v\|_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.
Categories: cs.IT cs.DS math.IT math.PR