A Simple Message-Passing Algorithm for Compressed Sensing

Details A Simple Message-Passing Algorithm for Compressed Sensing A Simple Message-Passing Algorithm for Compressed Sensing

2010-01-23

arxiv.org/abs/1001.4110v1

Computer Science

Information Theory

Scientific paper

We consider the recovery of a nonnegative vector x from measurements y = Ax, where A is an m-by-n matrix whos entries are in {0, 1}. We establish that when A corresponds to the adjacency matrix of a bipartite graph with sufficient expansion, a simple message-passing algorithm produces an estimate \hat{x} of x satisfying ||x-\hat{x}||_1 \leq O(n/k) ||x-x(k)||_1, where x(k) is the best k-sparse approximation of x. The algorithm performs O(n (log(n/k))^2 log(k)) computation in total, and the number of measurements required is m = O(k log(n/k)). In the special case when x is k-sparse, the algorithm recovers x exactly in time O(n log(n/k) log(k)). Ultimately, this work is a further step in the direction of more formally developing the broader role of message-passing algorithms in solving compressed sensing problems.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-514604