Princeton University

School of Engineering & Applied Science

Fitting Convex Sets to Data

Venkat Chandrasekaran, CalTech
B205 Engineering Quadrangle
Monday, March 11, 2019 - 4:30pm


A number of problems in signal processing may be viewed conceptually as fitting a convex set to data.  In vision and learning, the task of identifying a collection of features or atoms that provide a concise description of a dataset has been widely studied under the title of dictionary learning or sparse coding.  In convex-geometric terms, this problem entails learning a polytope with a desired facial structure from data.  In computed tomography, reconstructing a shape from support measurements arises commonly in MRI, robotics, and target reconstruction from radar data.  This problem is usually reformulated as one of estimating a polytope from a collection of noisy halfspaces.

In this talk we describe new approaches to these problems that leverage contemporary ideas from the optimization literature on lift-and-project descriptions of convex sets.  This perspective leads to natural semidefinite programming generalizations of previous techniques for fitting polyhedral convex sets to data.  We provide several stylized illustrations in which these generalizations provide improved reconstructions.  On the algorithmic front our methods rely prominently on operator scaling, while on the statistical side our analysis builds on links between learning theory and semialgebraic geometry.


Venkat Chandrasekaran is a Professor at Caltech in Computing and Mathematical Sciences and in Electrical Engineering.  He received a Ph.D. in Electrical Engineering and Computer Science in June 2011 from MIT, and a B.A. in Mathematics as well as a B.S. in Electrical and Computer Engineering in May 2005 from Rice University.  He was awarded the Jin-Au Kong Dissertation Prize for the best doctoral thesis in Electrical Engineering at MIT (2012), the Young Researcher Prize in Continuous Optimization (at the 4th ICCOPT of the Mathematical Optimization Society, 2013), the Sloan Research Fellowship in Mathematics (2016), and the INFORMS Optimization Society Prize for Young Researchers (2016).  He is currently serving as an Associate Editor for the Annals of Statistics, the SIAM Journal on the Mathematics of Data Science, and the SIAM Journal on Applied Algebra and Geometry.  His research interests broadly lie in mathematical optimization and its interface with topics in the information sciences.





This seminar is supported with funds from the Korhammer Lecture Series