# Efficient Discretizations of Optimal Transport

arXiv: https://arxiv.org/abs/2102.07956 · HTML: https://mlsanity.com/paper/2102.07956/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 16 Feb 2021.

## Builds on (most cited first, 9 of 9)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance](https://mlsanity.com/paper/1805.11897/) (2018)
- [A mathematical theory of cooperative communication](https://mlsanity.com/paper/1910.02822/) (2019)
- [Variational Bayes with Intractable Likelihood](https://mlsanity.com/paper/1503.08621/) (2015)
- [Much Faster Algorithms for Matrix Scaling](https://mlsanity.com/paper/1704.02315/) (2017)
- [Bayesian design of experiments for intractable likelihood models using coupled auxiliary models and multivariate emulation](https://mlsanity.com/paper/1803.07018/) (2018)
- [Sequential Cooperative Bayesian Inference](https://mlsanity.com/paper/2002.05706/) (2020)

## Abstract (arXiv)

Obtaining solutions to Optimal Transportation (OT) problems is typically intractable when the marginal spaces are continuous. Recent research has focused on approximating continuous solutions with discretization methods based on i.i.d. sampling, and has proven convergence as the sample size increases. However, obtaining OT solutions with large sample sizes requires intensive computation effort, that can be prohibitive in practice. In this paper, we propose an algorithm for calculating discretizations with a given number of points for marginal distributions, by minimizing the (entropy-regularized) Wasserstein distance, and result in plans that are comparable to those obtained with much larger numbers of i.i.d. samples. Moreover, a local version of such discretizations which is parallelizable for large scale applications is proposed. We prove bounds for our approximation and demonstrate performance on a wide range of problems.