Abstract: 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 use an approximate message passing (AMP) algorithm and show that it eectively solves the reconstruction problem at information-theoretically optimal rates. More specically, we show that the approach is successful as soon as the undersampling rate exceeds the (upper) 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. For `discrete' signals, i.e., signals whose coor- dinates take a xed nite set of values, this implies reconstruction from o(n) measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal pX. In the second part of the talk, I will 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.
Bio: Adel Javanmard is currently nishing the Ph.D. degree in the Department of Electri- cal Engineering at Stanford University, advised by Andrea Montanari. He received Master's degree in Electrical Engineering from Stanford University (2011), a Bachelor's degree in Elec- trical Engineering and a Bachelor's degree in Pure Mathematics both from Sharif University, Tehran (2009). During summers 2011 and 2012, he interned with Microsoft Research (MSR). His research interests include machine learning, high-dimensional statistics, graphical models, and convex optimization. He was awarded Stanford Electrical Engineering Fellowship (2009), and Stanford Graduate Fellowship (2010-2012).