A Simple Message-Passing Algorithm for Compressed Sensing
Recovery of a vector x from measurements of the form y = Ax has been of central interest in the compressed sensing literature. When restricted to binary vectors, this has been of interest in the context of binary linear error-correcting codes. In essence, both desire a matrix A and an estimation or decoding algorithm that allows for faithful recovery of x from y. In this paper, the authors study the performance of a message passing recovery algorithm when the matrix A corresponds to the adjacency matrix of a bipartite graph with good expansion properties. Results of a similar flavor are well-known in the context of coding, but have only begun to be explored in the context of compressed sensing.