Approximate Message Passing and the Blessing of Dimensionality

Friday, May 04, 2012

The problem of recovering a sparse signal from an underdetermined set of linear equations is paramount in many applications such as compressed sensing, genomics, and machine learning. While significant advances have been made in this area, providing useful insights and intuitions, many important questions are still open including the fundamental performance limits of the recovery algorithms. In this talk, I present a novel sparse recovery algorithm, referred to as approximate message passing (AMP), that uses the “blessing" of large dimensions to solve the ℓ1- norm regularized least squares or the LASSO problem very efficiently. In particular, AMP exhibits fast convergence and relies on inexpensive iterations, which renders it suitable for solving high-dimensional problems. Moreover, AMP provides a novel theoretical framework for analyzing the fundamental performance limits of the LASSO, by converting it into a sequence of classical signal plus noise estimation problems. I will show that this new framework settles several fundamental and practically      important questions such as the noise sensitivity of the LASSO.This talk is based on a joint work with David Donoho, Iain Johnstone, Richard Baraniuk,Andrea Montanari, Laura Anitori, and Zai Yang.


Arian Maleki received his Ph.D. in electrical engineering from Stanford University under the supervision of Prof. David Donoho in 2010. He then joined the DSP group at Rice University as apostdoctoral scholar. His research interests include massive data analysis, compressed sensing,machine learning, signal processing and optimization. He received his M.Sc. in statistics from Stanford University, and B.Sc. and M.Sc. both in electrical engineering from Sharif University of Technology.