Conference proceeding
On sharp performance bounds for robust sparse signal recoveries
2009 IEEE International Symposium on Information Theory, pp.493-497
06/2009
DOI: 10.1109/ISIT.2009.5205718
Abstract
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¿ senses (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.
Details
- Title: Subtitle
- On sharp performance bounds for robust sparse signal recoveries
- Creators
- Weiyu Xu - California Institute of TechnologyBabak Hassibi - California Institute of Technology
- Resource Type
- Conference proceeding
- Publication Details
- 2009 IEEE International Symposium on Information Theory, pp.493-497
- DOI
- 10.1109/ISIT.2009.5205718
- ISSN
- 2157-8095
- eISSN
- 2157-8117
- Publisher
- IEEE
- Language
- English
- Date published
- 06/2009
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197425102771
Metrics
70 Record Views