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

03/28/2019

∙

by   Shravas Rao, et al.

∙

0

∙

share

Let A be an N × N Fourier matrix over F_p^N/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 = Ω( ^2N), we show that Ω(kkN/p) rows must be sampled to satisfy the restricted isometry property with constant probability.