Message Passing Algorithms for Compressed Sensing

Details Message Passing Algorithms for Compressed Sensing Message Passing Algorithms for Compressed Sensing

2009-07-21

arxiv.org/abs/0907.3574v1

Computer Science

Information Theory

6 pages paper + 9 pages supplementary information, 13 eps figure. Submitted to Proc. Natl. Acad. Sci. USA

Scientific paper

Compressed sensing aims to undersample certain high-dimensional signals, yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity-undersampling tradeoff is achieved when reconstructing by convex optimization -- which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity-undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity-undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity-undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity-undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this new, apparently very different theoretical formalism.

Affiliated with

Also associated with

No associations

Rating

Message Passing Algorithms for Compressed Sensing 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 Message Passing Algorithms for Compressed Sensing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Message Passing Algorithms for Compressed Sensing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-175310