Approximation of Wasserstein distance with Transshipment
arXiv:1901.09400
Abstract
An algorithm for approximating the p-Wasserstein distance between histograms defined on unstructured discrete grids is presented. It is based on the computation of a barycenter constrained to be supported on a low dimensional subspace, which corresponds to a transshipment problem. A multi-scale strategy is also considered. The method provides sparse transport matrices and can be applied to large scale and non structured data.
References in corpus (10)
- Fast Computation of Wasserstein Barycenters
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
- A Sparse Multi-Scale Algorithm for Dense Optimal Transport
- Smooth and Sparse Optimal Transport
- An efficient linear programming method for Optimal Transportation
- The Shortlist Method for Fast Computation of the Earth Mover's Distance and Finding Optimal Solutions to Transportation Problems
- Stochastic Wasserstein Barycenters
- DOTmark - A Benchmark for Discrete Optimal Transport
- Statistical Optimal Transport via Factored Couplings
- Approximating the Quadratic Transportation Metric in Near-Linear Time