Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing

Adel Javanmard
Graduate Student, Stanford University
Given on: Feb. 15, 2013


We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. We show rigorously that message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements at information-theoretically optimal rates. More specifically, it recovers the signal as soon as the undersampling rate exceeds the Renyi information dimension of the signal. For sparse signals, i.e. sequences of dimension n and k(n) non-zero entries, this implies reconstruction from k(n)+o(n) measurements. If time allows, I will also discuss how the idea of spatial coupling can be implemented through Gabor transform in sampling theory.

This is based on joint work with David L. Donoho and Andrea Montanari.