Randomised Wasserstein Barycenter Computation: Resampling with Statistical Guarantees
arXiv:2012.06397
Abstract
We propose a hybrid resampling method to approximate finitely supported Wasserstein barycenters on large-scale datasets, which can be combined with any exact solver. Nonasymptotic bounds on the expected error of the objective value as well as the barycenters themselves allow to calibrate computational cost and statistical accuracy. The rate of these upper bounds is shown to be optimal and independent of the underlying dimension, which appears only in the constants. Using a simple modification of the subgradient descent algorithm of Cuturi and Doucet, we showcase the applicability of our method on a myriad of simulated datasets, as well as a real-data example from cell microscopy which are out of reach for state of the art algorithms for computing Wasserstein barycenters.
References in corpus (12)
- Geometric deep learning: going beyond Euclidean data
- Fast Computation of Wasserstein Barycenters
- Non-Euclidean statistics for covariance matrices, with applications to diffusion tensor imaging
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- Amplitude and phase variation of point processes
- Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
- A Sparse Multi-Scale Algorithm for Dense Optimal Transport
- A Fast Proximal Point Method for Computing Exact Wasserstein Distance
- An efficient linear programming method for Optimal Transportation
- Principal Geodesic Analysis for Probability Measures under the Optimal Transport Metric
- Multiscale Strategies for Computing Optimal Transport
- Stochastic Saddle-Point Optimization for Wasserstein Barycenters