On the recovery of nonnegative sparse vectors from sparse measurements inspired by expanders
Lists
Only you see this
Abstract
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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> 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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> 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.
BibTeX
@inproceedings{khajehnejad2009recovery,
author = {M. Amin Khajehnejad and Babak Hassibi},
title = {{On the recovery of nonnegative sparse vectors from sparse measurements inspired by expanders}},
booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
year = {2009},
doi = {10.1109/icassp.2009.4960227},
}Loading related content...