Improved bounds for the RIP of Subsampled Circulant matrices

2018/08/22 by Meng Huang, Yuxuan Pang, Huang, Meng +3 · 1 citation
Engineering · Mathematics · #Advanced Combinatorial Mathematics #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Mathematical Analysis and Transform Methods #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1808.07333

openalex publication_date 2018/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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²(s)log (n) rows randomly where n is the vector length. This improves the previously known bound m \gtrsim s log² slog² n.

Citations

• Atomic Decomposition by Basis Pursuit
• Stable signal recovery from incomplete and inaccurate measurements
• Iterative hard thresholding for compressed sensing

Cited by

• Improved RIP Bounds for Gaussian Partial Circulant Matrices

Related

• Improved RIP Bounds for Gaussian Partial Circulant Matrices
• Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
• Suprema of Chaos Processes and the Restricted Isometry Property
• Explicit construction of RIP matrices is Ramsey-hard
• New constructions of RIP matrices with fast multiplication and fewer rows