Nonnegative Compressed Sensing with Minimal Perturbed 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 construct sparse measurement matrices for the recovery of non-negative vectors, using perturbations of adjacency matrices of expander graphs with much smaller expansion coefficients than previously suggested schemes. These constructions are crucial in applications, such as DNA microarrays and sensor networks, where dense measurements are not practically feasible. We present a necessary and sufficient condition for lscr₁ optimization to successfully recover the unknown vector and obtain closed form expressions for the recovery threshold. We finally present a novel recovery algorithm that exploits expansion and is faster than lscr₁ optimization.