A simple message-passing algorithm for compressed sensing

Year
2010
Type(s)
Author(s)
V. Chandar, D. Shah, G. W. Wornell
Source
2010 IEEE International Symposium on Information Theory Proceedings (ISIT), Austin, TX, 2010, pp. 1968-1972
Url
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5513358

We consider the recovery of a nonnegative vector x from measurements y = Ax, where A ∈ {0, 1}m×n. 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 x^ of x satisfying ∥x-x^∥1 = O(n over k) ∥x−x(k)∥1, where x(k) is the best k-sparse approximation of x. The algorithm performs O(n(log(n over k))2 log(k)) computation in total, and the number of measurements required is m = O(k log(n over k)). In the special case when x is k-sparse, the algorithm recovers x exactly in time O(n log(n over 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.