Improved bounds for the RIP of subsampled circulant matrices

MaRDI QIDQ3379762zbMATH OpenFDO

Authors Meng Huang, Yuxuan Pang, Zhiqiang Xu

Publication date 27 September 2021

Full work available at URL https://arxiv.org/abs/1808.07333, http://stsip.org/pdf/vol18/vol18pp1-8.pdf

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)

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$.

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

Cites work

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

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

Describes a project that uses

Uses Software

• CoSaMP
• PDCO

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)