In a variety of research areas, the weighted bag of vectors and the histogram are widely used descriptors for complex objects. Both can be expressed as discrete distributions. D2-clustering pursues the minimum total within-cluster variation for a set of discrete distributions subject to the Kantorovich-Wasserstein metric. D2-clustering has a severe scalability issue, the bottleneck being the computation of a centroid distribution, called Wasserstein barycenter, that minimizes its sum of squared distances to the cluster members. In this paper, we develop a modified Bregman ADMM approach for computing the approximate discrete Wasserstein barycenter of large clusters. In the case when the support points of the barycenters are unknown and have low cardinality, our method achieves high accuracy empirically at a much reduced computational cost. The strengths and weaknesses of our method and its alternatives are examined through experiments, and we recommend scenarios for their respective usage. Moreover, we develop both serial and parallelized versions of the algorithm. By experimenting with large-scale data, we demonstrate the computational efficiency of the new methods and investigate their convergence properties and numerical stability. The clustering results obtained on several datasets in different domains are highly competitive in comparison with some widely used methods in the corresponding areas.
@cite_41: Wasserstein barycenters correspond to optimal solutions of transportation problems for several marginals, and as such have a wide range of applications ranging from economics to statistics and computer science. When the marginal probability measures are absolutely continuous (or vanish on small sets) the theory of Wasserstein barycenters is well-developed [see the seminal paper (Agueh and Carlier in SIAM J Math Anal 43(2):904–924, 2011)]. However, exact continuous computation of Wasserstein barycenters in this setting is tractable in only a small number of specialized cases. Moreover, in many applications data is given as a set of probability measures with finite support. In this paper, we develop theoretical results for Wasserstein barycenters in this discrete setting. Our results rely heavily on polyhedral theory which is possible due to the discrete structure of the marginals. The results closely mirror those in the continuous case with a few exceptions. In this discrete setting we establish that Wasserstein barycenters must also be discrete measures and there is always a barycenter which is provably sparse. Moreover, for each Wasserstein barycenter there exists a non-mass-splitting optimal transport to each of the discrete marginals. Such non-mass-splitting transports do not generally exist between two discrete measures unless special mass balance conditions hold. This makes Wasserstein barycenters in this discrete setting special in this regard. We illustrate the results of our discrete barycenter theory with a proof-of-concept computation for a hypothetical transportation problem with multiple marginals: distributing a fixed set of goods when the demand can take on different distributional shapes characterized by the discrete marginal distributions. A Wasserstein barycenter, in this case, represents an optimal distribution of inventory facilities which minimize the squared distance transportation cost totaled over all demands.
@cite_33: In this paper, we introduce a notion of barycenter in the Wasserstein space which generalizes McCann's interpolation to the case of more than two measures. We provide existence, uniqueness, characterizations, and regularity of the barycenter and relate it to the multimarginal optimal transport problem considered by Gangbo and Świech in [Comm. Pure Appl. Math., 51 (1998), pp. 23–45]. We also consider some examples and, in particular, rigorously solve the Gaussian case. We finally discuss convexity of functionals in the Wasserstein space.
Given @math arbitrary discrete distributions each with @math support points, their true Wasserstein barycenter in theory can be solved via linear programming @cite_33 @cite_41 . This is because the support points of the Wasserstein barycenter can only locate at a finite (yet huge) number of possible positions. However, solving the true discrete barycenter quickly becomes intractable even for a rather small number of distributions containing only 10 support points each. An important theoretical progress has been made by @cite_41 who proved that the actual support of a true barycenter of @math such distributions is extremely sparse, with cardinality @math no greater than @math . However, the complexity of the problem is not reduced practically because so far there is no theoretically ensured way to sift out the optimal sparse locations. On the other hand, the new theory seems to backup the practice of assuming a pre-selected number of support points in a barycenter as an approximation to the true solution.