Fitting convex sets to data

Abstract: 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.

algebraic topologycombinatoricsinformation theorymetric geometrynumerical analysisoptimization and controlstatistics theory

Audience: researchers in the topic

Mathematics of Data and Decisions @ Davis

Series comments: Description: Mathematical aspects of data science and decision-making

The zoom link is visible online, but you will need to get password. For this write, using a university account (!) to the current organizers email (this is public information).