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

Moein Khajehnejad, Babak Hassibi

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 = {Moein 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...

Figure