Logo image
Back
Compressed sensing over the Grassmann manifold: A unified analytical framework
Conference proceeding

Compressed sensing over the Grassmann manifold: A unified analytical framework

Weiyu Xu and Babak Hassibi
2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp.562-567
09/2008
DOI: 10.1109/ALLERTON.2008.4797608

View Online

Abstract

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.
 Geometry Linear Programming Signal Analysis basis pursuit Compressed sensing convex polytopes Equations geometric probability Grassmann angle Grassmann manifold high-dimensional integral geometry k-balancedness l 1 -optimization Manifolds neighborly polytopes Particle measurements random linear subspaces Size measurement Sufficient conditions Vectors

Details

Metrics

26 Record Views
26 Times Cited - Web of Science
Logo image