A Sparse Multi-Scale Algorithm for Dense Optimal Transport
arXiv:1510.05466 · doi:10.1007/s10851-016-0653-9
Abstract
Discrete optimal transport solvers do not scale well on dense large problems since they do not explicitly exploit the geometric structure of the cost function. In analogy to continuous optimal transport we provide a framework to verify global optimality of a discrete transport plan locally. This allows construction of an algorithm to solve large dense problems by considering a sequence of sparse problems instead. The algorithm lends itself to being combined with a hierarchical multi-scale scheme. Any existing discrete solver can be used as internal black-box.Several cost functions, including the noisy squared Euclidean distance, are explicitly detailed. We observe a significant reduction of run-time and memory requirements.
Published "online first" in Journal of Mathematical Imaging and Vision, see DOI
References in corpus (1)
Cited by in corpus (23)
- Scaling Algorithms for Unbalanced Transport Problems
- Stochastic Wasserstein Barycenters
- DOTmark - A Benchmark for Discrete Optimal Transport
- Optimal transport via a Monge-Ampère optimization problem
- Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
- Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning
- The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
- Approximation of Optimal Transport problems with marginal moments constraints
- Multilevel Optimal Transport: a Fast Approximation of Wasserstein-1 distances
- Optimal Transport: Fast Probabilistic Approximation with Exact Solvers
- Domain decomposition for entropy regularized optimal transport
- Image Labeling Based on Graphical Models Using Wasserstein Messages and Geometric Assignment
- An Interior-Point-Inspired algorithm for Linear Programs arising in Discrete Optimal Transport
- Set Representation Learning with Generalized Sliced-Wasserstein Embeddings
- On Coupling Particle Filter Trajectories
- 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
- Variational Wasserstein Barycenters for Geometric Clustering
- Approximation of Wasserstein distance with Transshipment
- Quantitative Stability and Error Estimates for Optimal Transport Plans
- Convex Histogram-Based Joint Image Segmentation with Regularized Optimal Transport Cost
- Approximating the Optimal Transport Plan via Particle-Evolving Method