The Convex Algebraic 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. A commonly encountered difficulty that arises in such inverse problems is the very limited availability of data relative to the ambient dimension of the signal to be estimated. We analyze a class of ill-posed linear inverse problems in which the underlying model of interest has simple algebraic structure. Specifically the focus of this talk is on the setting in which we are given a small number of linear measurements of a simple model, which is formed by adding a small number of elements from some atomic set. Examples of such 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 regularization framework to recover such simple models. We discuss general recovery guarantees for our approach, and describe several example applications. 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.

Bio : Venkat Chandrasekaran received the B.S. degree in electrical engineering and the B.A. degree in mathematics from Rice University in 2005. He received the S.M. degree in 2007 in electrical engineering from the Massachusetts Institute of Technology, where he is currently a Ph.D. candidate in the Laboratory for Information and Decision Systems. His research interests include optimization, statistics, and signal processing.

Webpage: http://ssg.mit.edu/~venkatc/