UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Large-scale inference, random convex problems, and the risk of the LASSO

Mathematical Physics & Probability

Speaker: Andrea Montanari, Stanford University
Location: 3106 MSB
Start time: Wed, Nov 17 2010, 4:10PM

The problem of estimating a high-dimensional vector from a set of linear observations arises in many areas of science and engineering. It becomes particularly challenging when the underlying signal has some non-linear structure that needs to be exploited. A reconstruction approach that ganed considerable popularity over the last few years consists in solving a suitable convex optimization problem, shose cost quantifies the quality of the solution. The analyisis of such procedures requires to characterize the optimum of a high dimensional random convex function. I will survey recent progress towards this goal, focusing on one specific such function, known as the LASSO, which is often used within compressed sensing applictons. Within a random measurements model, we prove an asymptotcally exact result on the distribution of the reconstruction vector. The analysis is unveils connections with the theory of graphical models, message passing algorithms and statistical mechanics. [Based on joint work with David L. Donoho and Arian Maleki, and with Mohsen Bayati and Jose Bento.]