Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 P/T Colloquia 
 Kac Lectures 
 Kac Fellows 
 Dist. Quant. Lecture 
 Ulam Scholar 
 CNLS Fellowship Application 
 Student Program 
 Past Visitors 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Monday, June 21, 2010
3:00 PM - 4:00 PM
CNLS Conference Room (TA-3, Bldg 1690)


Message passing algorithms, random convex problems, and the risk of the LASSO

Andrea Montanari
Stanford University

The problem of estimating a high-dimensional vector from a set of linear observations arises in a number of engineering disciplines. It becomes particularly challenging when the underlying signal has some non-linear structure that needs to be exploited. I will present a new class of iterative algorithms inspired by probabilistic graphical models ideas, that appear to be asymptotically optimal in specific contexts.

The analysis of these algorithms allows to prove remarkably sharp results on the asymptotic behavior of some families of random convex problems. I will in particular discuss the mean square error for LASSO estimation in the context of compressed sensing problems.

[Based on joint work with David L. Donoho and Arian Maleki, and with Mohsen Bayati and Jose Bento.]

Host: Vadas Gintautas