School Seminars and Colloquia

Optimal Phase Transitions in Compressed Sensing


by David Donoho

Institution: Stanford University
Date: Tue 8th May 2012
Time: 12:00 PM
Location: Richard Berry Building - Russell Love Theatre

Abstract: ``Compressed Sensing" is an active research area which touches on harmonic analysis, geometric functional analysis, applied mathematics, computer science, electrical engineering, mathematical statistics, and information theory. Concrete achievements, such as speeding up pediatric MRI acquistion times from 8 minutes to about one minute, are now entering daily use.

In my talk I will discuss the notion of phase transitions in combinatorial geometry, describe how they precisely demarcate the situations where a popular algorithm in compressed sensing -- \(\ell_1\) minimization -- can succeed. Then I will discuss the issue: what is the best possible phase transition of any algorithm? We get different answers depending on the assumptions we make. If we assume the distribution of the coefficients is known/unknown, we get different answers; in each case I describe novel algorithms precisely achieving the optimal phase transition. Both algorithms are applications of the Approximate Message Passing algorithm introduced by Maleki, Montanari and myself.

The basic tools for our results are information theory and statistical decision theory, which compared to popular approaches like Restricted Isometry Properties (Candes-Tao) and Geometric Functional Analysis (Rudelson Vershynin) give much more precise understanding of quantitative properties, where previously only order-of-magnitude bounds were known.

I will attempt to explain the new viewpoint that makes these very precise estimates possible, which has a number of surprising ingredients. Also I will attempt to explain to statisticians why these results are isomorphic to results about fitting linear models to noisy data in the high-dimensional \(p>>n\) case.

This talk surveys joint work with several authors, including Andrea Montanari and Jared Tanner, as well as Adel Javanmard, Iain Johnstone and Arian Maleki.

Colloquium Website