A geometrical stability condition for compressed sensing

DOI10.1016/J.LAA.2016.04.017zbMATH Open1350.94018arXiv1510.08241OpenAlexW1846305482MaRDI QIDQ286166FDOQ286166

Axel Flinth

Publication date: 20 May 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: During the last decade, the paradigm of compressed sensing has gained significant importance in the signal processing community. While the original idea was to utilize sparsity assumptions to design powerful recovery algorithms of vectors $xinmathbb{R}^d$, the concept has been extended to cover many other types of problems. A noteable example is low-rank matrix recovery. Many methods used for recovery rely on solving convex programs. A particularly nice trait of compressed sensing is its geometrical intuition. In recent papers, a classical optimality condition has been used together with tools from convex geometry and probability theory to prove beautiful results concerning the recovery of signals from Gaussian measurements. In this paper, we aim to formulate a geometrical condition for stability and robustness, i.e. for the recovery of approximately structured signals from noisy measurements. We will investigate the connection between the new condition with the notion of restricted singular values, classical stability and robustness conditions in compressed sensing, and also to important geometrical concepts from complexity theory. We will also prove the maybe somewhat surprising fact that for many convex programs, exact recovery of a signal $x_0$ immediately implies some stability and robustness when recovering signals close to $x_0$.

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

Recommendations

• The Geometry of Compressed Sensing
• Stability and instance optimality for Gaussian measurements in compressed sensing
• Compressed Sensing With Prior Information: Strategies, Geometry, and Bounds
• The geometry of off-the-grid compressed sensing
• Deterministic Constructions of Compressed Sensing Matrices From Unitary Geometry
• Compressive sensing with local geometric features
• An asymptotic existence result on compressed sensing matrices
• A generalization of the restricted isometry property and applications to compressed sensing
• A remark on compressed sensing
• Interactions between compressed sensing random matrices and high dimensional geometry

zbMATH Keywords

sparse recoverycompressed sensingconvex geometryGrassmannian condition number

Mathematics Subject Classification ID

Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Cites Work

• Stable signal recovery from incomplete and inaccurate measurements
• A mathematical introduction to compressive sensing
• Precise Stability Phase Transitions for $\ell_1$ Minimization: A Unified Geometric Framework
• Some perturbation theory for linear programming
• A geometric analysis of Renegar's condition number, and its interplay with conic curvature
• The convex geometry of linear inverse problems
• Title not available (Why is that?)
• On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements
• A Coordinate-Free Condition Number for Convex Programming
• Living on the edge: phase transitions in convex programs with random data
• Recovering Compressively Sampled Signals Using Partial Support Information
• Signal Space CoSaMP for Sparse Recovery With Redundant Dictionaries

Cited In (4)

• A Data-Independent Distance to Infeasibility for Linear Conic Systems
• The Geometry of Compressed Sensing
• Compressed sensing construction for underdetermined source separation
• A Geometrical Study of Matching Pursuit Parametrization

Uses Software

• CoSaMP

This page was built for publication: A geometrical stability condition for compressed sensing

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