Loading…

On the recovery of nonnegative sparse vectors from sparse measurements inspired by expanders

This paper studies compressed sensing for the recovery of non-negative sparse vectors from a smaller number of measurements than the ambient dimension of the unknown vector. We focus on measurement matrices that are sparse, i.e., have only a constant number of nonzero (and non-negative) entries in e...

Full description

Saved in:
Bibliographic Details
Main Authors: Khajehnejad, M.A., Hassibi, B.
Format: Conference Proceeding
Language:English
Subjects:
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper studies compressed sensing for the recovery of non-negative sparse vectors from a smaller number of measurements than the ambient dimension of the unknown vector. We focus on measurement matrices that are sparse, i.e., have only a constant number of nonzero (and non-negative) entries in each column. For such measurement matrices we give a simple necessary and sufficient condition for l 1 optimization to successfully recover the unknown vector. Using a simple ldquoperturbationrdquo to the adjacency matrix of an unbalanced expander, we obtain simple closed form expressions for the threshold relating the ambient dimension n, number of measurements m and sparsity level k, for which l 1 optimization is successful with overwhelming probability. Simulation results suggest that the theoretical thresholds are fairly tight and demonstrate that the ldquoperturbationsrdquo significantly improve the performance over a direct use of the adjacency matrix of an expander graph.
ISSN:1520-6149
2379-190X
DOI:10.1109/ICASSP.2009.4960227