CaltechAUTHORS
  A Caltech Library Service

Compressive Sensing over the Grassmann Manifold: a Unified Geometric Framework

Xu, Weiyu and Hassibi, Babak (2010) Compressive Sensing over the Grassmann Manifold: a Unified Geometric Framework. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20150129-073448689

[img] PDF - Submitted Version
See Usage Policy.

479Kb

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

Abstract

ℓ_1 minimization is often used for finding the sparse solutions of an under-determined linear system. In this paper we focus on finding sharp performance bounds on recovering approximately sparse signals using ℓ_1 minimization, possibly 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 (The "sparsity" in this paper means the size of the set of nonzero or significant elements in a signal vector.) level can be quite loose. The neighborly polytope analysis which yields sharp bounds for ideally sparse signals cannot be readily generalized to approximately sparse signals. Starting from a necessary and sufficient condition, the "balancedness" property of linear subspaces, for achieving a certain signal recovery accuracy, we give a unified null space Grassmann angle-based geometric framework for analyzing the performance of ℓ_1 minimization. By investigating the "balancedness" property, this unified framework characterizes sharp quantitative tradeoffs between the considered sparsity and the recovery accuracy of the ℓ_1 optimization. As a consequence, this generalizes the neighborly polytope result for ideally 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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1005.3729arXivDiscussion Paper
Additional Information:This work was supported in part by the National Science Foundation under grant no. CCF-0729203, by the David and Lucille Packard Foundation, and by Caltech’s Lee Center for Advanced Networking.
Funders:
Funding AgencyGrant Number
NSFCCF-0729203
Caltech’s Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20150129-073448689
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150129-073448689
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54216
Collection:CaltechAUTHORS
Deposited By: Shirley Slattery
Deposited On:30 Jan 2015 22:45
Last Modified:30 Jan 2015 22:45

Repository Staff Only: item control page