Fast Computation of Wasserstein Barycenters

By Marco Cuturi, Arnaud Doucet. 2013

825 citations recorded by the source corpus.

We present new algorithms to compute the mean of a set of empirical probability measures under the optimal transport metric. This mean, known as the Wasserstein barycenter, is the measure that minimizes the sum of its Wasserstein distances to each element in that set. We propose two original algorithms to compute Wasserstein barycenters that build upon the subgradient method. A direct implementation of these algorithms is, however, too costly because it would require the repeated resolution of large primal and dual optimal transport problems to compute subgradients. Extending the work of Cuturi (2013), we propose to smooth the Wasserstein distance used in the definition of Wasserstein barycenters with an entropic regularizer and recover in doing so a strictly convex objective whose gradients can be computed for a considerably cheaper computational cost using matrix scaling algorithms. We use these algorithms to visualize a large family of images and to solve a constrained clustering problem.

Subfields: Applied Mathematics, Computational Theory and Mathematics, Radiology, Nuclear Medicine and Imaging, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Theory and Mathematics

In Radiology, Nuclear Medicine and Imaging

In Optimization & Training

Citations in the corpus

GAIT: A Geometric Approach to Information Theory (2019, methodology): “…(Goodfellow et al., 2014; Arjovsky et al., 2017; Salimans et al., 2018); and (ii) the development of alternative formulations and relaxations of the original optimal transport objective which make it feasible to approximately compute in practice (Cuturi and Doucet, 2014; Genevay et al., 2018).”
Model Fusion via Optimal Transport (2019, methodology): “The resulting layer-wise averaging scheme can be interpreted as computing the Wasserstein barycenter [3, 4] of the probability measures defined at the corresponding layers of the parent models.”
Learning Generative Models with Sinkhorn Divergences (2017, background): “One distinction lies in the fact that they do not back-propagate errors across the Sinkhorn iterations, but rather use an estimate of the optimal transport matrix to compute an upper-bound on the Sinkhorn divergence, as was done for instance in [11]”
Computational Optimal Transport (2018, methodology): “One can thus implement a gradient descent to compute a local minimizer of EL, as used, for instance, in [Cuturi and Doucet, 2014].”
Theoretical Analysis of Domain Adaptation with Optimal Transport (2016, methodology): “It turns out that the Wasserstein distance has been successfully used in various applications, for instance: computer vision [22], texture analysis [21], tomographic reconstruction [12] and clustering [9].”
Optimal Transport for Domain Adaptation (2014, background): “However, new computing strategies have emerged [5], [15], [17] and made possible the application of OTdistances in operational settings.”
Consistent estimation of a population barycenter in the Wasserstein space (2013, background): “There also exists a growing interest on the development of fast algorithms for the computation of empirical barycenters with various applications in image processing [6, 15].”
Supervised Word Mover's Distance (2016, methodology): “In fact, computing this gradient just for a single pair of documents will require time complexity O(q(3) log q), where q is the largest set of unique words in either document [8].”
Rectify Heterogeneous Models with Semantic Mapping (2018, methodology): “For example, in image query (Rubner et al., 1998), document classification (Huang et al., 2016), domain adaptation (Perrot et al., 2016; Courty et al., 2017a;b), and barycenter discovery (Cuturi & Doucet, 2014).”
Heterogeneous Few-Shot Model Rectification With Semantic Mapping (2020, background): “For example, in image query [56], document classiﬁcation [57], domain adaptation [21], [22], [58], and barycenter discovery [59].”
A General Approach to Fairness with Optimal Transport (2020, methodology): “Solving this regularized objective can be done efﬁciently via the Sinkhorn algorithm (Cuturi and Doucet 2014), which achieves a linear convergence rate (Altschuler, Weed, and Rigollet 2017).”
A Fast Proximal Point Method for Computing Wasserstein Distance (2018, methodology): “We compare our method with state-of-art Sinkhorn based methods [8], [31] and [5].”
A Fast Proximal Point Method for Computing Exact Wasserstein Distance (2018, methodology): “From the top to the bottom, we show (top row) the demo of input data; (second row) the results based on [9]; (third row) the result based on [35]; (fourth row) the result based on [5]; (bottom row) the results based on IPOT-WB.”
Inference for empirical Wasserstein distances on finite spaces (2016, background): “Barycentres in the Wasserstein space (Agueh and Carlier, 2011) have recently received much attention (Cuturi and Doucet, 2014; Del Barrio et al., 2015).”
Fréchet means and Procrustes analysis in Wasserstein space (2017, methodology): “In this direction, Cuturi & Doucet [27] employ differentiability properties and carry out what could be thought of as a “gradient descent”, a discrete analogue of Algorithm 1; Benamou et al. [11] exploit the structure of the constraints as an intersection of convex sets by means of iterating Bregman”
A fixed-point approach to barycenters in Wasserstein space (2015, background): “This appealing concept shows a high potential for application, already considered in Artiﬁcial Intelligence or in Statistics (see, e.g., [16], [5], [10], [20], [7] or [3]).”