  Compressive sensing (CS) is a sampling technique designed for reducing the
complexity of sparse data acquisition. One of the major obstacles for practical
deployment of CS techniques is the signal reconstruction time and the high
storage cost of random sensing matrices. We propose a new structured
compressive sensing scheme, based on codes of graphs, that allows for a joint
design of structured sensing matrices and logarithmic-complexity reconstruction
algorithms. The compressive sensing matrices can be shown to offer
asymptotically optimal performance when used in combination with Orthogonal
Matching Pursuit (OMP) methods. For more elaborate greedy reconstruction
schemes, we propose a new family of list decoding belief propagation
algorithms, as well as reinforced- and multiple-basis belief propagation
algorithms. Our simulation results indicate that reinforced BP CS schemes offer
very good complexity-performance tradeoffs for very sparse signal vectors.
