Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data

Algebra & Discrete Mathematics

Speaker: Jacob Miller, UC Davis
Location: 2112 MSB Math Science Building
Start time: Wed, May 25 2016, 5:10PM

2-Wasserstein barycenters correspond to optimal solutions of transportation problems with several marginals, and can be viewed as a type of weighted averaging minimizing the squared 2-Wasserstein distance. The case when the marginal probability measures are absolutely continuous have been of recent interest and have become well-developed. However, in many applications, data is given as discrete probability measures with finite support. We present theoretical results for Wasserstein barycenters in the discrete case, relying heavily on polyhedral theory.

In particular, our results closely mirror those in the continuous case. We estabilish existence of these barycenters in the discrete case, show that they are also discrete, and that the size of their support can also be linear in the size of the support of the marginals. We show that optimal transport maps exist between these barycenters and the original discrete marginals, and analog to the continuous case. Finally, we utilize the discrete transportation problem to show that discrete Wasserstein geodesics can be computed in strongly-polynomial time. This is joint work with E. Anderes and S. Borgwardt.

Ph.D Exit seminar