A Caltech Library Service

Sparse Recovery of Nonnegative Signals With Minimal Expansion

Khajehnejad, M. Amin and Dimakis, Alexandros G. and Xu, Weiyu and Hassibi, Babak (2011) Sparse Recovery of Nonnegative Signals With Minimal Expansion. IEEE Transactions on Signal Processing, 59 (1). pp. 196-208. ISSN 1053-587X.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We investigate the problem of reconstructing a high-dimensional nonnegative sparse vector from lower-dimensional linear measurements. While much work has focused on dense measurement matrices, sparse measurement schemes can be more efficient both with respect to signal sensing as well as reconstruction complexity. Known constructions use the adjacency matrices of expander graphs, which often lead to recovery algorithms which are much more efficient than l_1 minimization. However, prior constructions of sparse measurement matrices rely on expander graphs with very high expansion coefficients which make the construction of such graphs difficult and the size of the recoverable sets very small. In this paper, we introduce sparse measurement matrices for the recovery of nonnegative vectors, using perturbations of the adjacency matrices of expander graphs requiring much smaller expansion coefficients, hereby referred to as minimal expanders. We show that when l_1 minimization is used as the reconstruction method, these constructions allow the recovery of signals that are almost three orders of magnitude larger compared to the existing theoretical results for sparse measurement matrices. We provide for the first time tight upper bounds for the so called weak and strong recovery thresholds when l_1 minimization is used. We further show that the success of l_1 optimization is equivalent to the existence of a “unique” vector in the set of solutions to the linear equations, which enables alternative algorithms for l_1 minimization. We further show that the defined minimal expansion property is necessary for all measurement matrices for compressive sensing, (even when the non-negativity assumption is removed) therefore implying that our construction is tight. We finally present a novel recovery algorithm that exploits expansion and is much more computationally efficient compared to l_1 minimization.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2011 IEEE. Manuscript received March 25, 2010; accepted September 16, 2010. Date of publication October 04, 2010; date of current version December 17, 2010. This work was supported in part by the National Science Foundation by Grants CCF-0729203, CNS-0932428, and CCF-1018927, by the Office of Naval Research under the MURI Grant N00014-08-1-0747, and by Caltech’s Lee Center for Advanced Networking. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Trac D. Tran.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-08-1-0747
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Compressed sensing, l_1 minimization, expander graphs
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number11704223
Issue or Number:1
Record Number:CaltechAUTHORS:20110610-094646559
Persistent URL:
Official Citation:Khajehnejad, M.A.; Dimakis, A.G.; Weiyu Xu; Hassibi, B.; , "Sparse Recovery of Nonnegative Signals With Minimal Expansion," Signal Processing, IEEE Transactions on , vol.59, no.1, pp.196-208, Jan. 2011 doi: 10.1109/TSP.2010.2082536
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:23969
Deposited By: Jason Perez
Deposited On:13 Jun 2011 19:58
Last Modified:03 Oct 2019 02:51

Repository Staff Only: item control page