Computational Optimal Transport

Abstract

Optimal transport (OT) theory can be informally described using the words of the French mathematician Gaspard Monge (1746-1818): A worker with a shovel in hand has to move a large pile of sand lying on a construction site. The goal of the worker is to erect with all that sand a target pile with a prescribed shape (for example, that of a giant sand castle). Naturally, the worker wishes to minimize her total effort, quantified for instance as the total distance or time spent carrying shovelfuls of sand. Mathematicians interested in OT cast that problem as that of comparing two probability distributions, two different piles of sand of the same volume. They consider all of the many possible ways to morph, transport or reshape the first pile into the second, and associate a "global" cost to every such transport, using the "local" consideration of how much it costs to move a grain of sand from one place to another. Recent years have witnessed the spread of OT in several fields, thanks to the emergence of approximate solvers that can scale to sizes and dimensions that are relevant to data sciences. Thanks to this newfound scalability, OT is being increasingly used to unlock various problems in imaging sciences (such as color or texture processing), computer vision and graphics (for shape manipulation) or machine learning (for regression, classification and density fitting). This short book reviews OT with a bias toward numerical methods and their applications in data sciences, and sheds lights on the theoretical properties of OT that make it particularly useful for some of these applications.

arXiv commentnew version with corrected typo in Eq. 4.43 and 4.44 (minus sign in front of f, g now changed to +) a few more corrected typos

Cited by in corpus (21)

• Unsupervised Hyperalignment for Multilingual Word Embeddings
• Sinkhorn Divergences for Unbalanced Optimal Transport
• Unsupervised Alignment of Embeddings with Wasserstein Procrustes
• Semi-dual Regularized Optimal Transport
• Improving Sequence-to-Sequence Learning via Optimal Transport
• Massively scalable Sinkhorn distances via the Nyström method
• Blind Source Separation with Optimal Transport Non-negative Matrix Factorization
• Ground Metric Learning on Graphs
• Approximating the Quadratic Transportation Metric in Near-Linear Time
• (q,p)-Wasserstein GANs: Comparing Ground Metrics for Wasserstein GANs
• GDPP: Learning Diverse Generations Using Determinantal Point Process
• On Scalable and Efficient Computation of Large Scale Optimal Transport
• Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory
• Unbalanced Sobolev Descent
• Weakly supervised cross-domain alignment with optimal transport
• Constructing sampling schemes via coupling: Markov semigroups and optimal transport
• Fast and Simple Mixture of Softmaxes with BPE and Hybrid-LightRNN for Language Generation
• k-GANs: Ensemble of Generative Models with Semi-Discrete Optimal Transport
• Error control for statistical solutions
• Introducing user-prescribed constraints in Markov chains for nonlinear dimensionality reduction
• Discriminative Clustering with Representation Learning with any Ratio of Labeled to Unlabeled Data