Fitting Convex Sets to Data

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.