Journal article
Precise Stability Phase Transitions for ℓ1 Minimization: A Unified Geometric Framework
IEEE transactions on information theory, Vol.57(10), pp.6894-6919
2011
DOI: 10.1109/TIT.2011.2165825
Abstract
ℓ 1 minimization is often used for recovering sparse signals from an under-determined linear system. In this paper, we focus on finding sharp performance bounds on recovering approximately sparse signals using ℓ 1 minimization under noisy measurements. While the restricted isometry property is powerful for the analysis of recovering approximately sparse signals with noisy measurements, the known bounds on the achievable sparsity1 level can be quite loose. The neighborly polytope analysis which yields sharp bounds for perfectly sparse signals cannot be readily generalized to approximately sparse signals. We start from analyzing a necessary and sufficient condition, the “balancedness” property of linear subspaces, for achieving a certain signal recovery accuracy. Then we give a unified null space Grassmann angle-based geometric framework to give sharp bounds on this “balancedness” property of linear subspaces. By investigating the “balancedness” property, this unified framework characterizes sharp quantitative tradeoffs between signal sparsity and the recovery accuracy of ℓ 1 minimization for approximately sparse signal. As a consequence, this generalizes the neighborly polytope result for perfectly sparse signals. Besides the robustness in the “strong” sense for all sparse signals, we also discuss the notions of “weak” and “sectional” robustness. Our results concern fundamental properties of linear subspaces and so may be of independent mathematical interest.
Details
- Title: Subtitle
- Precise Stability Phase Transitions for ℓ1 Minimization: A Unified Geometric Framework
- Creators
- WEIYU XU - Department of Electrical Engineering, California Institute of Technology, Pasadena, CA, 91125, United StatesBabak HASSIBI - Department of Electrical Engineering, California Institute of Technology, Pasadena, CA, 91125, United States
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on information theory, Vol.57(10), pp.6894-6919
- Publisher
- Institute of Electrical and Electronics Engineers
- DOI
- 10.1109/TIT.2011.2165825
- ISSN
- 0018-9448
- eISSN
- 1557-9654
- Language
- English
- Date published
- 2011
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984083263002771
Metrics
24 Record Views