CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20111101-085058069

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

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111101-085058069

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 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
http://dx.doi.org/10.1109/TIT.2011.2165825DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6034753&tag=1PublisherUNSPECIFIED
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.
Funders:
Funding AgencyGrant Number
NSFCCF-0729203
NSFCNS-0932428
NSFCCF-1018927
Office of Naval Research (ONR) Multidisciplinary University Research Initiative (MURI) N00014-08-1-0747
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20111101-085058069
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20111101-085058069
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: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6034753&isnumber=6034704
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27543
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:01 Nov 2011 16:17
Last Modified:23 Aug 2016 10:07

Repository Staff Only: item control page