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

DOI10.1007/978-3-030-69637-5_18zbMATH Open1481.94049arXiv1408.4409OpenAlexW1959156040MaRDI QIDQ5020144FDOQ5020144

Dustin G. Mixon, Jameson Cahill

Publication date: 4 January 2022

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

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.

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

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?

zbMATH Keywords

random matricessensing operators

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Simultaneous analysis of Lasso and Dantzig selector
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Restricted eigenvalue properties for correlated Gaussian designs
• Model Selection and Estimation in Regression with Grouped Variables
• Title not available (Why is that?)
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Title not available (Why is that?)
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Decoding by Linear Programming
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A simple proof of the restricted isometry property for random matrices
• Adaptive estimation of a quadratic functional by model selection.
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Stable image reconstruction using total variation minimization
• Compressed sensing and best 𝑘-term approximation
• A mathematical introduction to compressive sensing
• Title not available (Why is that?)
• The Generic Chaining
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• A remark on compressed sensing
• On sparse reconstruction from Fourier and Gaussian measurements
• Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
• The restricted isometry property and its implications for compressed sensing
• The convex geometry of linear inverse problems
• Certifying the Restricted Isometry Property is Hard
• Bounding the Smallest Singular Value of a Random Matrix Without Concentration
• Title not available (Why is that?)
• Living on the edge: phase transitions in convex programs with random data
• Recovering Compressively Sampled Signals Using Partial Support Information
• Suprema of chaos processes and the restricted isometry property
• Derandomizing restricted isometries via the Legendre symbol
• New constructions of RIP matrices with fast multiplication and fewer rows
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
• Title not available (Why is that?)
• Interpolation via weighted \(\ell_{1}\) minimization
• Block-Sparse Recovery via Convex Optimization
• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Compressed Sensing: How Sharp Is the Restricted Isometry Property?
• Robust Recovery of Signals From a Structured Union of Subspaces
• Reconstruction and subgaussian processes
• Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization

Cited In (5)

• A Data-Independent Distance to Infeasibility for Linear Conic Systems
• Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
• 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

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)