Improved bounds for the RIP of subsampled circulant matrices

zbMATH Open1470.65072arXiv1808.07333MaRDI QIDQ3379762FDOQ3379762

Authors: Meng Huang, Yuxuan Pang, Zhiqiang Xu 

Publication date: 27 September 2021

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 $mgtrsimslo{g}^2(s)log(n)$ rows randomly where $n$ is the vector length. This improves the previously known bound $mgtrsimslo{g}^{2}slo{g}^{2}n$.

Full work available at URL: https://arxiv.org/abs/1808.07333

Recommendations

• Restricted isometries for partial random circulant matrices
• An Improved Estimate in the Restricted Isometry Problem
• Suprema of chaos processes and the restricted isometry property
• The restricted isometry property of subsampled Fourier matrices

zbMATH Keywords

restricted isometry property (RIP)partial random circulant matricessubgaussian random vectors

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Stable signal recovery from incomplete and inaccurate measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• A mathematical introduction to compressive sensing
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• Sparse Approximate Solutions to Linear Systems
• On sparse reconstruction from Fourier and Gaussian measurements
• An Improved Estimate in the Restricted Isometry Problem
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Atomic decomposition by basis pursuit
• Suprema of chaos processes and the restricted isometry property
• Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation
• Compressive sensing and structured random matrices
• Compressive sensing by random convolution
• Hard thresholding pursuit: an algorithm for compressive sensing
• Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants
• The performance of orthogonal multi-matching pursuit under the restricted isometry property
• Improved bounds for sparse recovery from subsampled random convolutions

Cited In (6)

• Improved matrix algorithms via the subsampled randomized Hadamard transform
• Breaking the k ² barrier for explicit RIP matrices
• Restricted isometries for partial random circulant matrices
• New bounds for circulant Johnson-Lindenstrauss embeddings
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Suprema of chaos processes and the restricted isometry property

Uses Software

• PDCO
• CoSaMP

This page was built for publication: Improved bounds for the RIP of subsampled circulant matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3379762)