Conference proceeding
Compressed sensing over the Grassmann manifold: A unified analytical framework
2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp.562-567
09/2008
DOI: 10.1109/ALLERTON.2008.4797608
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.
Details
- Title: Subtitle
- Compressed sensing over the Grassmann manifold: A unified analytical framework
- Creators
- Weiyu Xu - California Institute of TechnologyBabak Hassibi - California Institute of Technology
- Resource Type
- Conference proceeding
- Publication Details
- 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp.562-567
- DOI
- 10.1109/ALLERTON.2008.4797608
- Publisher
- IEEE
- Language
- English
- Date published
- 09/2008
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197111802771
Metrics
26 Record Views