A Caltech Library Service

Precise Stability Phase Transitions for ℓ_1 Minimization: A Unified Geometric Framework

Xu, Weiyu and Hassibi, Babak (2011) Precise Stability Phase Transitions for ℓ_1 Minimization: A Unified Geometric Framework. IEEE Transactions on Information Theory, 57 (10). pp. 6894-6919. ISSN 0018-9448.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


ℓ_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 sparsity 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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2011 IEEE. Manuscript received June 02, 2010; revised December 21, 2010; accepted June 22, 2011. Date of current version October 06, 2011. The work of B. Hassibi was supported in part by the National Science Foundation under Grants CCF-0729203, CNS-0932428, and CCF-1018927, by the Office of Naval Research under the MURI Grant 00014-08-1-0747, and by Caltech’s Lee Center for Advanced Networking. Parts of this paper first appeared in the 46th Annual Allerton Conference on Communications, Control, and Computing, September 2008, and at the IEEE International Symposium on Information Theory, July 2009. Communicated by J. Romberg, Associate Editor for Signal Processing.
Funding AgencyGrant Number
Office of Naval Research (ONR) Multidisciplinary University Research Initiative (MURI)N00014-08-1-0747
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Issue or Number:10
Record Number:CaltechAUTHORS:20111101-085058069
Persistent URL:
Official Citation:Xu, W.; Hassibi, B.; , "Precise Stability Phase Transitions for \ell _1 Minimization: A Unified Geometric Framework," Information Theory, IEEE Transactions on , vol.57, no.10, pp.6894-6919, Oct. 2011 doi: 10.1109/TIT.2011.2165825 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27543
Deposited By: Ruth Sustaita
Deposited On:01 Nov 2011 16:17
Last Modified:03 Oct 2019 03:24

Repository Staff Only: item control page