Improved bounds for the RIP of Subsampled Circulant matrices
For researchers in compressed sensing and signal processing, this tightens the theoretical guarantees for circulant measurement matrices, which are computationally efficient.
The paper improves the bound for the restricted isometry property of partial random circulant matrices from m ≳ s log² s log² n to m ≳ s log² s log n, showing that fewer measurements suffice for high-probability recovery.
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\gtrsim s \log^2(s)\log (n)$ rows randomly where $n$ is the vector length. This improves the previously known bound $m \gtrsim s \log^2 s\log^2 n$.