A simple message-passing algorithm for compressed sensing

V. Chandar, D. Shah, G. W. Wornell
2010 IEEE International Symposium on Information Theory Proceedings (ISIT), Austin, TX, 2010, pp. 1968-1972

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.