Fast Computation of Wasserstein Barycenters

Abstract

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.

9 pages, 4 figures

References in corpus (2)

• Testing for Homogeneity with Kernel Fisher Discriminant Analysis
• Learning Probability Measures with respect to Optimal Transport Metrics

Cited by in corpus (175)

• Statistical Aspects of Wasserstein Distances
• Learning with a Wasserstein Loss
• Soft-DTW: a Differentiable Loss Function for Time-Series
• On Markov chain Monte Carlo methods for tall data
• Estimating individual treatment effect: generalization bounds and algorithms
• Amplitude and phase variation of point processes
• Wasserstein Discriminant Analysis
• A Fast Proximal Point Method for Computing Exact Wasserstein Distance
• Scaling Algorithms for Unbalanced Transport Problems
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• Obtaining fairness using optimal transport theory
• Stochastic Wasserstein Barycenters
• Missing Data Imputation using Optimal Transport
• Multilevel Clustering via Wasserstein Means
• Progressive Wasserstein Barycenters of Persistence Diagrams
• Semi-dual Regularized Optimal Transport
• Gradient descent algorithms for Bures-Wasserstein barycenters
• Principal Geodesic Analysis for Probability Measures under the Optimal Transport Metric
• Generalization Bounds and Representation Learning for Estimation of Potential Outcomes and Causal Effects
• Wasserstein barycenters are NP-hard to compute
• DESCN: Deep Entire Space Cross Networks for Individual Treatment Effect Estimation
• On the Complexity of Approximating Multimarginal Optimal Transport
• On the Complexity of Approximating Wasserstein Barycenter
• Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projections
• Unbalanced Multi-Marginal Optimal Transport
• A Divide-and-Conquer Bayesian Approach to Large-Scale Kriging
• An Optimal Transport Approach to Personalized Federated Learning
• optimalFlow: Optimal-transport approach to flow cytometry gating and population matching
• An asymptotic analysis of distributed nonparametric methods
• Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
• Scalable Computations of Wasserstein Barycenter via Input Convex Neural Networks
• A Survey on Optimal Transport for Machine Learning: Theory and Applications
• Continuous Regularized Wasserstein Barycenters
• Globally Optimal Joint Image Segmentation and Shape Matching Based on Wasserstein Modes
• Deep Learning for Learning Graph Representations
• Adversarial Computation of Optimal Transport Maps
• Greedy stochastic algorithms for entropy-regularized optimal transport problems
• Ground Metric Learning on Graphs
• All of the Fairness for Edge Prediction with Optimal Transport
• Wasserstein Training of Boltzmann Machines
• Debiased Sinkhorn barycenters
• Linear Time Sinkhorn Divergences using Positive Features
• Optimal Transport: Fast Probabilistic Approximation with Exact Solvers
• Approximating the Quadratic Transportation Metric in Near-Linear Time
• Differentiable Particle Filtering via Entropy-Regularized Optimal Transport
• Differentiable Ranks and Sorting using Optimal Transport
• Are Few-Shot Learning Benchmarks too Simple ? Solving them without Task Supervision at Test-Time
• An explicit analysis of the entropic penalty in linear programming
• Empirical geodesic graphs and CAT(k) metrics for data analysis
• Differentiable Deep Clustering with Cluster Size Constraints
• The statistical effect of entropic regularization in optimal transportation
• Multi-Source Domain Adaptation through Dataset Dictionary Learning in Wasserstein Space
• Unsupervised Multilingual Alignment using Wasserstein Barycenter
• A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters
• On the Computation of Kantorovich-Wasserstein Distances between 2D-Histograms by Uncapacitated Minimum Cost Flows
• Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification
• Validated Variational Inference via Practical Posterior Error Bounds
• A Smoothed Dual Approach for Variational Wasserstein Problems
• Stochastic Optimization for Regularized Wasserstein Estimators
• Optimal Transport losses and Sinkhorn algorithm with general convex regularization
• Generalized conditional gradient: analysis of convergence and applications
• Learning Wasserstein Embeddings
• Continuous Wasserstein-2 Barycenter Estimation without Minimax Optimization
• The GenCol algorithm for high-dimensional optimal transport: general formulation and application to barycenters and Wasserstein splines
• Estimating Barycenters of Measures in High Dimensions
• Entropic-Wasserstein barycenters: PDE characterization, regularity and CLT
• SurvITE: Learning Heterogeneous Treatment Effects from Time-to-Event Data
• Model Fusion via Optimal Transport
• Co-clustering through Optimal Transport
• Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support
• Wasserstein barycenters can be computed in polynomial time in fixed dimension
• Optimal quantization of the mean measure and applications to statistical learning
• A contribution to Optimal Transport on incomparable spaces
• Wide Consensus for Parallelized Inference
• Network Consensus in the Wasserstein Metric Space of Probability Measures
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space
• Learning Individual Causal Effects from Networked Observational Data
• On clustering uncertain and structured data with Wasserstein barycenters and a geodesic criterion for the number of clusters
• Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem
• Inference for Empirical Wasserstein Distances on Finite Spaces
• Numerical methods for matching for teams and Wasserstein barycenters
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Projected Statistical Methods for Distributional Data on the Real Line with the Wasserstein Metric
• Computing Kantorovich-Wasserstein Distances on $d$-dimensional histograms using $(d+1)$-partite graphs
• Averaging Atmospheric Gas Concentration Data using Wasserstein Barycenters
• Wasserstein K-Means for Clustering Tomographic Projections
• Entropic Wasserstein Gradient Flows
• Fuzzy c-Means Clustering for Persistence Diagrams
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification
• Tree-Wasserstein Barycenter for Large-Scale Multilevel Clustering and Scalable Bayes
• Wasserstein Measure Coresets
• Projection Robust Wasserstein Barycenters
• Conditional Wasserstein Barycenters and Interpolation/Extrapolation of Distributions
• Making transport more robust and interpretable by moving data through a small number of anchor points
• Randomised Wasserstein Barycenter Computation: Resampling with Statistical Guarantees
• Relaxed Earth Mover's Distances for Chain- and Tree-connected Spaces and their use as a Loss Function in Deep Learning
• Augmented Sliced Wasserstein Distances
• Wasserstein Embedding for Graph Learning
• Flow-based Alignment Approaches for Probability Measures in Different Spaces
• Feature Robust Optimal Transport for High-dimensional Data
• CPOT: Channel Pruning via Optimal Transport
• Quantum geometry of correlated many-body states
• Sinkhorn Barycenter via Functional Gradient Descent
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters
• Distributionally robust halfspace depth
• Variational Wasserstein Barycenters for Geometric Clustering
• Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe
• Landmarks Augmentation with Manifold-Barycentric Oversampling
• Geometric Losses for Distributional Learning
• Barycentric-alignment and reconstruction loss minimization for domain generalization
• Optimal Transport for Diffeomorphic Registration
• Correcting Nuisance Variation using Wasserstein Distance
• Discrete Wasserstein Barycenters: Optimal Transport for Discrete Data
• Fast Topological Clustering with Wasserstein Distance
• Counterfactual Cross-Validation: Stable Model Selection Procedure for Causal Inference Models
• Entropy-regularized Optimal Transport Generative Models
• Distributed Learning of Finite Gaussian Mixtures
• Iterative Bregman Projections for Regularized Transportation Problems
• A Balancing Weight Framework for Estimating the Causal Effect of General Treatments
• Super-efficiency of automatic differentiation for functions defined as a minimum
• Image Data Compression for Covariance and Histogram Descriptors
• Stability of Entropic Wasserstein Barycenters and application to random geometric graphs
• Application of an unbalanced optimal transport distance and a mixed L1/Wasserstein distance to full waveform inversion
• Searching equillibriums in large transport networks
• Wasserstein k-means with sparse simplex projection
• Double Robust Representation Learning for Counterfactual Prediction
• On the Existence of Optimal Transport Gradient for Learning Generative Models
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
• Sketching Merge Trees for Scientific Data Visualization
• Sampling From the Wasserstein Barycenter
• Fixed Support Tree-Sliced Wasserstein Barycenter
• Volume Preserving Image Segmentation with Entropic Regularization Optimal Transport and Its Applications in Deep Learning
• Optimal Fusion of Elliptic Extended Target Estimates based on the Wasserstein Distance
• Causal Inference on Distribution Functions
• On Regularized Square-root Regression Problems: Distributionally Robust Interpretation and Fast Computations
• Residual Networks as Flows of Velocity Fields for Diffeomorphic Time Series Alignment
• A novel notion of barycenter for probability distributions based on optimal weak mass transport
• Sliced Multi-Marginal Optimal Transport
• ALLWAS: Active Learning on Language models in WASserstein space
• Matching Distributions via Optimal Transport for Semi-Supervised Learning
• Distribution Mismatch Correction for Improved Robustness in Deep Neural Networks
• On Efficient Multilevel Clustering via Wasserstein Distances
• Approximation of Wasserstein distance with Transshipment
• Regularized Wasserstein Means for Aligning Distributional Data
• Temporal Wasserstein non-negative matrix factorization for non-rigid motion segmentation and spatiotemporal deconvolution
• A Sinkhorn-Newton method for entropic optimal transport
• Learning Optimal Transport Between two Empirical Distributions with Normalizing Flows
• Discovering Invariances in Healthcare Neural Networks
• Wasserstein total variation filtering
• A Linear Transportation ${\mathrm{L}}^p$ Distance for Pattern Recognition
• Robust Unsupervised Learning of Temporal Dynamic Interactions
• Zero-Shot Recognition via Optimal Transport
• Approximating the Optimal Transport Plan via Particle-Evolving Method
• Shape-Constrained Density Estimation via Optimal Transport
• Selective information exchange in collaborative clustering using regularized Optimal Transport
• Multiview Sensing With Unknown Permutations: An Optimal Transport Approach
• Low-Rank Sinkhorn Factorization
• Continual Learning of Generative Models with Limited Data: From Wasserstein-1 Barycenter to Adaptive Coalescence
• Optimal transport problems regularized by generic convex functions: A geometric and algorithmic approach
• Efficient estimates of optimal transport via low-dimensional embeddings
• Permutation invariant networks to learn Wasserstein metrics
• Computing Wasserstein Barycenter via operator splitting: the method of averaged marginals
• The Fourier Discrepancy Function
• Estimation and Quantization of Expected Persistence Diagrams
• Convex optimization
• Variational Wasserstein Barycenters with c-Cyclical Monotonicity
• Quantifying error in estimates of human brain fiber directions using Earth Mover's Distance
• On Cross-Layer Alignment for Model Fusion of Heterogeneous Neural Networks
• Counterfactual Maximum Likelihood Estimation for Training Deep Networks
• Riemannian-geometric generalizations of quantum fidelities and Bures-Wasserstein distance
• Coupling Matrix Manifolds and Their Applications in Optimal Transport
• Fast Optimal Transport Averaging of Neuroimaging Data
• On Inductive Biases for Machine Learning in Data Constrained Settings