A Caltech Library Service

On sharp performance bounds for robust sparse signal recoveries

Xu, Weiyu and Hassibi, Babak (2009) On sharp performance bounds for robust sparse signal recoveries. In: ISIT 2009. IEEE , Piscataway, NJ, pp. 493-497. ISBN 978-1-4244-4312-3.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


It is well known in compressive sensing that l_1 minimization can recover the sparsest solution for a large class of underdetermined systems of linear equations, provided the signal is sufficiently sparse. In this paper, we compute sharp performance bounds for several different notions of robustness in sparse signal recovery via l_1 minimization. In particular, we determine necessary and sufficient conditions for the measurement matrix A under which l_1 minimization guarantees the robustness of sparse signal recovery in the "weak", "sectional" and "strong" (e.g., robustness for "almost all" approximately sparse signals, or instead for "all" approximately sparse signals). Based on these characterizations, we are able to compute sharp performance bounds on the tradeoff between signal sparsity and signal recovery robustness in these various senses. Our results are based on a high-dimensional geometrical analysis of the null-space of the measurement matrix A. These results generalize the thresholds results for purely sparse signals and also present generalized insights on l_1 minimization for recovering purely sparse signals from a null-space perspective.

Item Type:Book Section
Related URLs:
Additional Information:© 2009 IEEE.
Subject Keywords:compressed sensing; basis pursuit; Grassmann angle; geometric probability; random linear subspaces
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number10842236
Record Number:CaltechAUTHORS:20100816-144533590
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:19448
Deposited By: Tony Diaz
Deposited On:16 Aug 2010 22:07
Last Modified:03 Oct 2019 01:57

Repository Staff Only: item control page