Distributed Computation of Wasserstein Barycenters over Networks

Optimal Transport distances (also known as earth mover's distances or Wasserstein distances) design an optimal plan to move "mass" from one probability distribution to another. This problem can be traced back to the early work of Monge [1] and Kantorovich [2] and has been of constant interest for allowing natural formulations to the problems of comparing, interpolating, and measuring distances of functions [3]. On the other hand, computational optimal transport has gain popularity for its applications in learning theory [4], computer vision [5], computer graphics [6], statistical inference [7], information fusion [8]; and its relative complexity advantages with respect to classical methods [9]. Particularly, large-scale optimal transport has been of recent interest for the latest applications where large quantities of data are available and efficient algorithms are required [10, 11, 12]. Comprehensive accounts of the optimal transport problem and its computational aspects can be found in [13, 14, 15, 3]. One of the common uses of the Wasserstein distance is the aggregation of distributions by considering their barycenter [16], which itself is another distribution [17]. Wasserstein Barycenters has been shown superior to traditional Euclidean-based methods in a range of application such as image processing [16], economics and finance [18] and condensed matter physics [19]. Figure 1 shows a sample of 100 images of the digit 7 from the MNIST dataset [20] and their respective Euclidean mean and Wasserstein mean.