The Convex Geometry of Inverse Problems

Benjamin Recht
University of Wisconsin-Madison
Computer Sciences

Building on the success of generalizing compressed sensing to matrix completion, this talk discusses progress on further extending 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 signals into sums of atomic signals from a simple but not necessarily discrete set. These algorithms are derived in a convex optimization framework that generalizes previous methods based on l1-norm minimization and nuclear norm minimization for recovering sparse vectors and low-rank matrices. I will discuss general recovery guarantees for this approach and describe several example applications. I will also describe how to scale these decomposition algorithms to very large data sets by exploiting structure to enable parallel, incremental implementations.

Presentation (PDF File)

Back to Workshop II: Numerical Methods for Continuous Optimization