A simple message-passing algorithm for compressed sensing

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))² 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.