Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


The Convex Geometry of Inverse Problems

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. In this talk, I will propose a unified approach 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 a convex 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 provide sharp estimates of the number of generic measurements required for exact and robust recovery of a variety of structured models. I will then detail several example applications and describe how to scale the corresponding inference algorithms to massive data sets.

Type of Seminar:
Optimization and Applications Seminar
Prof. Ben Recht
Computer Sciences Department, University of Wisconsin, USA
May 20, 2011   16:30

G 19.1, ETH main buidling, Rämistrasse 101
Contact Person:

John Lygeros
No downloadable files available.
Biographical Sketch:
Benjamin Recht is an Assistant Professor in the Department of Computer Sciences at the University of Wisconsin-Madison and holds courtesy appointments in Electrical and Computer Engineering and Mathematics. He is a PI in the Wisconsin Institute for Discovery (WID), a newly founded center aimed at bringing together researchers from a broad spectrum of disciplines to study problems at the convergence of information technology, biotechnology, and nanotechnology. Ben received his B.S. with honors in Mathematics from the University of Chicago, and received a M.S. in 2002 and PhD from the MIT Media Laboratory. After completing his doctoral work, he was a postdoctoral fellow in the Center for the Mathematics of Information at Caltech, a multidisciplinary center established to promote information science and technology.