Compressed sensing can drastically speed up axquisition of signals and
images in many applications (eg MRI, radar) by deliberately undersampling and using nonlinear optimization to beat the traditional sampling theory limits. In only a few years it became a popular research area in applied harmonic analysis, information theory, and statistical signal processing, spawning hundreds of papers and some significant applications -- for example speeding up pediatric MRIs from 8 minutes to about 1 minute, as shown in pinnacle journals in Radiology.
The most popular mathematical approach, due to Cand\`es, Tao and collaborators,
involves asymptotic order bounds; one uses random matrix theory, combinatorics and
hard analysis techniques to obtain order bounds how much an object can be undersampled and yet still recovered.
A less well-known approach due to myself and Tanner is based on counting faces of random polytopes; it is quantitatively precise. In my talk I will compare these two established approaches and some of their
successes and mention other interesting approaches.
Then I will discuss a very recent approach which is quantitatively
precise, but gives rise to precise information about many topics
that previously eluded precise analysis: noise sensitivity, sparsity sensitivity, alternate definitions
of sparsity, models of block sparsity, optimal nonconvex optimization. I'll describe some of these
new results, which are quite easy to digest as compared to earlier results and formulations.
Best of all the new results include a family of algorithms, approximate message passing,
which are dramatically faster than the standard 'fast' methods popular today.