An efficient linear programming method for Optimal Transportation
arXiv:1509.03668
Abstract
An efficient method for computing solutions to the Optimal Transportation (OT) problem with a wide class of cost functions is presented. The standard linear programming (LP) discretization of the continuous problem becomes intractible for moderate grid sizes. A grid refinement method results in a linear cost algorithm. Weak convergence of solutions is stablished. Barycentric projection of transference plans is used to improve the accuracy of solutions. The method is applied to more general problems, including partial optimal transportation, and barycenter problems. Computational examples validate the accuracy and efficiency of the method. Optimal maps between nonconvex domains, partial OT free boundaries, and high accuracy barycenters are presented.
25 pages, 11 figures, 2 tables
References in corpus (1)
Cited by in corpus (24)
- A Sparse Multi-Scale Algorithm for Dense Optimal Transport
- Sliced-Wasserstein Autoencoder: An Embarrassingly Simple Generative Model
- DOTmark - A Benchmark for Discrete Optimal Transport
- Transport-based analysis, modeling, and learning from signal and data distributions
- Regularized Optimal Transport and the Rot Mover's Distance
- Multilevel Optimal Transport: a Fast Approximation of Wasserstein-1 distances
- Genuine Quantum Chaos and Physical Distance Between Quantum States
- A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters
- Learning a Domain-Invariant Embedding for Unsupervised Domain Adaptation Using Class-Conditioned Distribution Alignment
- Set Representation Learning with Generalized Sliced-Wasserstein Embeddings
- Least action principles for incompressible flows and geodesics between shapes
- Randomised Wasserstein Barycenter Computation: Resampling with Statistical Guarantees
- A Transportation Distance for Signal Analysis
- Analysis and Application of Optimal Transport For Challenging Seismic Inverse Problems
- GANs with Conditional Independence Graphs: On Subadditivity of Probability Divergences
- Minimal convex extensions and finite difference discretization of the quadratic Monge-Kantorovich problem
- A data-driven linear-programming methodology for optimal transport
- Approximation of Wasserstein distance with Transshipment
- Quantitative Stability and Error Estimates for Optimal Transport Plans
- Discovery and visualization of structural biomarkers from MRI using transport-based morphometry
- A continuation multiple shooting method for Wasserstein geodesic equation
- Optimal Transport Aggregation for Distributed Mixture-of-Experts
- Approximating the Optimal Transport Plan via Particle-Evolving Method
- A Linear Transportation Distance for Pattern Recognition