We investigate the sparse recovery problem of reconstructing a high-dimensional non-negative sparse vector from lower dimensional linear measurements. While initial work focused on dense measurement matrices, such as those arising from Gaussian ensembles, sparse measurement schemes have been constructed recently, using the adjacency matrices of expander graphs. These constructions are crucial in applications, such as DNA microarrays and sensor networks, where dense measurements are not practically feasible. Furthermore, they often lead to recovery algorithms much more efficient than $\ell_1$ minimization. However, to date, constructions based on expanders have required very high expansion coefficients which can potentially make the construction of such graphs difficult and the size of the recoverable sets small. 

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. We present a necessary and sufficient condition for $\ell_1$ optimization to successfully recover the unknown vector and obtain expressions for the recovery threshold. We further show that the minimal expansion we use is necessary for any graph for which sparse recovery is possible and that therefore our construction is tight. We finally present a novel recovery algorithm that exploits expansion and is much faster than $\ell_1$ optimization. We determine theoretical guarantees about the sparsity level of the recoverable vectors for this algorithm and compare it to existing schemes in the literature.