On sharp performance bounds for robust sparse signal recoveries
- Creators
- Xu, Weiyu
- Hassibi, Babak
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" (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.
Additional Information
© 2009 IEEE.Attached Files
Published - Xu2009p110992009_Ieee_International_Symposium_On_Information_Theory_Vols_1-_4.pdf
Files
Name | Size | Download all |
---|---|---|
md5:6e39edbd97e4ec56cf603ffbbe8d2c25
|
941.8 kB | Preview Download |
Additional details
- Eprint ID
- 19448
- Resolver ID
- CaltechAUTHORS:20100816-144533590
- Created
-
2010-08-16Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 10842236