## Imaging and Computing Seminar

### Venkat Chandrasekaran , EECS, MIT

**Title:**

The Convex Geometry of Linear Inverse Problems

**Abstract:**

Deducing the state or structure of a system from partial, noisy measurements is
a fundamental task throughout the sciences and engineering. The resulting
inverse problems are often ill-posed because there are fewer measurements
available than the ambient dimension of the model to be estimated. In practice,
however, many interesting signals or models contain few degrees of freedom
relative to their ambient dimension: a small number of genes may constitute the
signature of a disease, very few parameters may specify the correlation
structure of a time series, or a sparse collection of geometric constraints may
determine a molecular configuration. Discovering, leveraging, or recognizing
such low-dimensional structure plays an important role in making inverse
problems well-posed. Examples of structured models include previously studied
cases such as sparse signals and low-rank matrices, as well as others such as
low-rank tensors, binary vectors, orthogonal matrices, and matrices formed as
the sum of a few permutations. Inspired by the success of the L1-norm and
nuclear-norm heuristics, we propose a general convex relaxation framework to
recover such simple structured models from partial information. We provide
sharp estimates of the number of generic measurements required for exact and
robust recovery in a variety of settings. These estimates are based on
computing certain Gaussian statistics related to the underlying model geometry.
Thus our work extends the catalog of objects and structures (beyond sparse
vectors and low-rank matrices) that can be recovered from limited information
via tractable convex programming.
Joint work with Benjamin Recht, Pablo Parrilo, and Alan Willsky.