MADDD-VenkatChandrasekaran

From Jesus De Loera May 17, 2020

113 plays 0 comments You unliked the media.

05/12 presentation by Venkat Chandrasekaran (Caltech)

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

Appears In: MADDD = Math of Data and Decisions @ UC Davis

Comments
Related Media

Loading…

MADDD-VenkatChandrasekaran

Related Media