as a metric, we can interpolate in the space of probability measure. [@mccann1997convexity] laid the foundation; [@agueh2011barycenters] developed the problem into a general scenario and coined the term “*Wasserstein barycenters*”. [@cuturi2014fast; @ho2017multilevel; @mi2018variational] relate WBs to K-means like clustering problems and [@leclaire2019fast; @lee2019hierarchical] explored the use of OT for hierarchical clustering. [@claici2018stochastic] is among the latest work on scalable semi-discrete Wasserstein barycenters. Most of them follow Kantorovich’s static OT; few of them follow Monge’s, or Brenier’s, dynamic version that regards OT as a gradient flow in the probability space.

Compared to previous work, our contribution is three-fold:

1\) We derive the WB based on Monge’s OT formulation and explore its connections to different clustering problems; 2) We prove the metric properties of our WB and propose it as a metric for evaluating multi-marginal clustering algorithms; 3) We explore the advantages and disadvantages of Monge WB through empirical comparison with other methods.

Primer on Optimal Transportation {#sec:primer}
================================

We begin by iterating key concepts of optimal transportation (OT), variational OT, and Wasserstein barycenters (WBs). Suppose $\MU, \NU$ are *Borel probability distributions* supported in *Polish spaces* $\X(\x)$, $\Y(\y)$, respectively. Let $\MUS(\X \times \Y)$ be the set of all probability distributions on $\X 