Title: The Convex Geometry of 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. This is joint work with Benjamin Recht, Pablo Parrilo, and Alan Willsky. Bio: Venkat Chandrasekaran is an assistant professor in the Department of Computing and Mathematical Sciences at Caltech. He received a Ph.D. in Electrical Engineering and Computer Science from MIT in 2011, and undergraduate degrees in Mathematics and in Electrical and Computer Engineering from Rice University in 2005. His research interests are in mathematical optimization and its application to problems in the information sciences.
