Sparse Recovery of Positive Signals with Minimal Expansion

Details Sparse Recovery of Positive Signals with Minimal Expansion Sparse Recovery of Positive Signals with Minimal Expansion

2009-02-24

arxiv.org/abs/0902.4045v1

Computer Science

Information Theory

25 pages, submitted for publication

Scientific paper

We investigate the sparse recovery problem of reconstructing a high-dimensional non-negative sparse vector from lower dimensional linear measurements. While much work has focused on dense measurement matrices, sparse measurement schemes are crucial in applications, such as DNA microarrays and sensor networks, where dense measurements are not practically feasible. One possible construction uses the adjacency matrices of expander graphs, which often leads 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. In this paper, we construct sparse measurement matrices for the recovery of non-negative vectors, using perturbations of the adjacency matrix of an expander graph with much smaller expansion coefficient. We present a necessary and sufficient condition for $\ell_1$ optimization to successfully recover the unknown vector and obtain expressions for the recovery threshold. For certain classes of measurement matrices, this necessary and sufficient condition is further equivalent to the existence of a "unique" vector in the constraint set, which opens the door to alternative algorithms to $\ell_1$ minimization. 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. Finally, we demonstrate through theoretical bounds, as well as simulation, that our method is robust to noise and approximate sparsity.

Affiliated with

Also associated with

No associations

Rating

Sparse Recovery of Positive Signals with Minimal Expansion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparse Recovery of Positive Signals with Minimal Expansion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse Recovery of Positive Signals with Minimal Expansion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-171749