A Convex View of Inverse Problems

Abstract: Deducing the state or structure of a system from partial, noisy
measurements is a fundamental task in science 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. For example, 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 network
configuration. Discovering, leveraging, or recognizing such low-dimensional
structure plays an important role in making inverse problems well-posed.

In this talk, I will propose a methodology to transform notions of
simplicity and latent low-dimensionality into convex penalty functions.
This approach builds on the success of generalizing compressed sensing to
matrix completion and greatly extends the catalog of objects and structures
that can be recovered from partial information. I will focus on a suite of
data analysis algorithms designed to decompose general signals into sums of
atoms from a simple---but not necessarily discrete---set. These algorithms
are derived in an optimization framework that encompasses previous methods
based on l1-norm minimization and nuclear norm minimization for recovering
sparse vectors and low-rank matrices.  I will contextualize these results
in several example applications.