Improved bounds for the RIP of Subsampled Circulant matrices
In this paper, we study the restricted isometry property of partial random circulant matrices. For a bounded subgaussian generator with independent entries, we prove that the partial random circulant matrices satisfy s-order RIP with high probability if one chooses m≳ s ^2(s) (n) rows randomly where n is the vector length. This improves the previously known bound m ≳ s ^2 s^2 n.
READ FULL TEXT