A Caltech Library Service

Compressed Sensing over the Grassmann Manifold: A Unified Analytical Framework

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. 562-567. ISBN 978-1-4244-2925-7.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


It is well known that compressed sensing problems reduce to finding the sparse solutions for large under-determined 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 non-convex 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 high-dimensional geometry, we give a unified null-space Grassmannian angle-based 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:
URLURL TypeDescription
Additional Information:© 2008 IEEE. Issue Date: 23-26 Sept. 2008; Date of Current Version: 04 March 2009.
Funding AgencyGrant Number
David and Lucile Packard FoundationUNSPECIFIED
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:compressed sensing; basis pursuit; l1-optimization; k-balancedness; Grassmann manifold; Grassmann angle; high-dimensional integral geometry; geometric probability; convex polytopes; random linear subspaces; neighborly polytopes
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number10501108
Record Number:CaltechAUTHORS:20100729-100253548
Persistent URL:
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.562-567, 23-26 Sept. 2008 doi: 10.1109/ALLERTON.2008.4797608 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:19216
Deposited By: Jason Perez
Deposited On:29 Jul 2010 22:56
Last Modified:03 Oct 2019 01:53

Repository Staff Only: item control page