Restricted Isometries for Partial Random Circulant Matrices

Abstract

In the theory of compressed sensing, restricted isometry analysis has become a standard tool for studying how efficiently a measurement matrix acquires information about sparse and compressible signals. Many recovery algorithms are known to succeed when the restricted isometry constants of the sampling matrix are small. Many potential applications of compressed sensing involve a data-acquisition process that proceeds by convolution with a random pulse followed by (nonrandom) subsampling. At present, the theoretical analysis of this measurement technique is lacking. This paper demonstrates that the $s$th order restricted isometry constant is small when the number $m$ of samples satisfies $m\gtrsim (s\log n{)}^{3/2}$, where $n$ is the length of the pulse. This bound improves on previous estimates, which exhibit quadratic scaling.

References in corpus (2)

• Identification of Matrices having a Sparse Representation
• The Gelfand widths of ${\ell }_p$-balls for $0<p\le 1$

Cited by in corpus (14)

• Measure What Should be Measured: Progress and Challenges in Compressive Sensing
• RSP-Based Analysis for Sparsest and Least ${\ell }_1$-Norm Solutions to Underdetermined Linear Systems
• Polynomial Fourier Domain as a Domain of Signal Sparsity
• The Faber-Krahn inequality for the Short-time Fourier transform
• Quasi-Linear Compressed Sensing
• Suprema of Chaos Processes and the Restricted Isometry Property
• Random Subsets of Structured Deterministic Frames have MANOVA Spectra
• Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
• Symmetric Toeplitz-Structured Compressed Sensing Matrices
• Compressed Sensing Based on Random Symmetric Bernoulli Matrix
• Nonlinear approximation with nonstationary Gabor frames
• Preconditioning filter bank decompositions using structured normalized tight frames
• Mixed Compressed Sensing Based on Random Graphs
• Analog Coding Frame-work