Robust width: a characterization of uniformly stable and robust compressed sensing

DOI10.1007/978-3-030-69637-5_18MaRDI QIDQ5020144zbMATH OpenOpenAlexFDO

Authors Jameson Cahill, Dustin G. Mixon

Publication date 4 January 2022

Published in Applied and Numerical Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

random matricessensing operators

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52)

Abstract: Compressed sensing seeks to invert an underdetermined linear system by exploiting additional knowledge of the true solution. Over the last decade, several instances of compressed sensing have been studied for various applications, and for each instance, reconstruction guarantees are available provided the sensing operator satisfies certain sufficient conditions. In this paper, we completely characterize the sensing operators which allow uniformly stable and robust reconstruction by convex optimization for many of these instances. The characterized sensing operators satisfy a new property we call the robust width property, which simultaneously captures notions of widths from approximation theory and of restricted eigenvalues from statistical regression. We provide a geometric interpretation of this property, we discuss its relationship with the restricted isometry property, and we apply techniques from geometric functional analysis to find random matrices which satisfy the property with high probability.

Recommendations

• On robust width property for Lasso and Dantzig selector
• Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
• An introduction to compressed sensing
• A geometrical stability condition for compressed sensing
• Compressed sensing: how sharp is the restricted isometry property?

Cites work

• scientific article; zbMATH DE number 4061904 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 194093 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A mathematical introduction to compressive sensing
• A remark on compressed sensing
• A simple proof of the restricted isometry property for random matrices
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Adaptive estimation of a quadratic functional by model selection.
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Block-Sparse Recovery via Convex Optimization
• Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Bounding the smallest singular value of a random matrix without concentration
• Certifying the Restricted Isometry Property is Hard
• Compressed sensing
• Compressed sensing and best \(k\)-term approximation
• Compressed sensing: how sharp is the restricted isometry property?
• Compressive sensing and structured random matrices
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Decoding by Linear Programming
• Derandomizing restricted isometries via the Legendre symbol
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Interpolation via weighted \(\ell_{1}\) minimization
• Living on the edge: phase transitions in convex programs with random data
• Model Selection and Estimation in Regression with Grouped Variables
• Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
• New constructions of RIP matrices with fast multiplication and fewer rows
• On sparse reconstruction from Fourier and Gaussian measurements
• Reconstruction and subgaussian processes
• Recovering Compressively Sampled Signals Using Partial Support Information
• Restricted eigenvalue properties for correlated Gaussian designs
• Restricted isometry of Fourier matrices and list decodability of random linear codes
• Robust Recovery of Signals From a Structured Union of Subspaces
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Simultaneous analysis of Lasso and Dantzig selector
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
• Stable image reconstruction using total variation minimization
• Suprema of chaos processes and the restricted isometry property
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• The Generic Chaining
• The convex geometry of linear inverse problems
• The restricted isometry property and its implications for compressed sensing

Cited in

(6)

• Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
• A data-independent distance to infeasibility for linear conic systems
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Robust and stable region-of-interest tomographic reconstruction using a robust width prior
• Discrete uncertainty principles and sparse signal processing
• On robust width property for Lasso and Dantzig selector

This page was built for publication: Robust width: a characterization of uniformly stable and robust compressed sensing

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