Optimization and Compressive Sensing

Modern technology depends on the acquisition, storage, and the processing of vast amounts of data. 

For many applications the data has an underlying simplicity that allows it to be greatly compressed, popular examples being the JPEG and MP3 image and audio compression standards. So far, compression is normally only possible after the full high-resolution data set has been acquired.

A major breakthrough in recent years, known under the name of Compressive Sensing, has been the discovery that compressible data can be efficiently acquired directly in a compressed form and a high quality approximation of the full data recovered by modern optimisation methods. Mathematically, the underlying problems can be formulated as problems of recovering sparse (or otherwise "simple") solutions to underdetermined systems of equations.

An important role in these developments is played by Convex Optimization, a methodology that includes computational approaches such as linear and semidefinite programming and has found countless applications in engineering, statistics and data science. One example is the famous method of $\ell_1$ minimization, which seeks to find a sparse solution of a system of equations (or low-dimensional statistical model) by minimizing the $\ell_1$-norm subject to linear constraints.

Work in this group focuses on fundamental problem in convex optimization, and its applications to compressive sensing and related fields.

Recent work in this group has lead to a complete understanding of the Phase Transition phenomenon in convex optimization: the chance of convex optimization works at recovering a signal changes abruptly from negligible to overwhelming as the number of measurements or observations moves past some threshold. The problems involved lead naturally to deep mathematical ideas from probability theory, functional analysis, convex analysis and geometry. For an overview of the field, see here.


▲ Up to the top