Xu, Weiyu and Hassibi, Babak (2009) Compressed Sensing over the Grassmann Manifold: A Unified Analytical Framework. In: 46th Annual Allerton Conference on Communication, Control, and Computing. IEEE , pp. 562567. ISBN 9781424429257. http://resolver.caltech.edu/CaltechAUTHORS:20100729100253548

PDF
 Published Version
See Usage Policy. 234Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20100729100253548
Abstract
It is well known that compressed sensing problems reduce to finding the sparse solutions for large underdetermined systems of equations. Although finding the sparse solutions in general may be computationally difficult, starting with the seminal work of [2], it has been shown that linear programming techniques, obtained from an l_(1)norm relaxation of the original nonconvex problem, can provably find the unknown vector in certain instances. In particular, using a certain restricted isometry property, [2] shows that for measurement matrices chosen from a random Gaussian ensemble, l_1 optimization can find the correct solution with overwhelming probability even when the support size of the unknown vector is proportional to its dimension. The paper [1] uses results on neighborly polytopes from [6] to give a ldquosharprdquo bound on what this proportionality should be in the Gaussian measurement ensemble. In this paper we shall focus on finding sharp bounds on the recovery of ldquoapproximately sparserdquo signals (also possibly under noisy measurements). While the restricted isometry property can be used to study the recovery of approximately sparse signals (and also in the presence of noisy measurements), the obtained bounds can be quite loose. On the other hand, the neighborly polytopes technique which yields sharp bounds for ideally sparse signals cannot be generalized to approximately sparse signals. In this paper, starting from a necessary and sufficient condition for achieving a certain signal recovery accuracy, using highdimensional geometry, we give a unified nullspace Grassmannian anglebased analytical framework for compressive sensing. This new framework gives sharp quantitative tradeoffs between the signal sparsity and the recovery accuracy of the l_1 optimization for approximately sparse signals. As it will turn out, the neighborly polytopes result of [1] for ideally sparse signals can be viewed as a special case of ours. Our result concerns fundamental properties of linear subspaces and so may be of independent mathematical interest.
Item Type:  Book Section  

Related URLs: 
 
Additional Information:  © 2008 IEEE. Issue Date: 2326 Sept. 2008; Date of Current Version: 04 March 2009.  
Funders: 
 
Subject Keywords:  compressed sensing; basis pursuit; l1optimization; kbalancedness; Grassmann manifold; Grassmann angle; highdimensional integral geometry; geometric probability; convex polytopes; random linear subspaces; neighborly polytopes  
Other Numbering System: 
 
Record Number:  CaltechAUTHORS:20100729100253548  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20100729100253548  
Official Citation:  Weiyu Xu; Hassibi, B.; , "Compressed sensing over the Grassmann manifold: A unified analytical framework," Communication, Control, and Computing, 2008 46th Annual Allerton Conference on , vol., no., pp.562567, 2326 Sept. 2008 doi: 10.1109/ALLERTON.2008.4797608 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4797608&isnumber=4797526  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  19216  
Collection:  CaltechAUTHORS  
Deposited By:  Jason Perez  
Deposited On:  29 Jul 2010 22:56  
Last Modified:  07 Jan 2015 20:52 
Repository Staff Only: item control page