Introduction to Optimal Transport and OTT

We talked about Wasserstein distance in the last lesson. It’s quite important to get a background of the underlying theory of optimal transport (OT) first.

Note: This lesson is a basic introduction to optimal transport (OT). It can be skipped if needed.

Optimal transport

In 1781, French mathematician Gaspard Monge presented the following problem:

_“A worker with a shovel in hand has to move a large pile of sand lying on a construction site. The worker’s goal is to erect a target pile with a prescribed shape (for example, a giant sandcastle). Naturally, the worker wishes to minimize her total effort, quantified, for instance, as the total distance or time spent carrying shovelfuls of sand.”
[G. Monge, Mémoire sur la théorie des déblais et des remblais (De l’Imprimerie Royale, 1781)]

So the problem is quite clear:

• We have a distribution $\mathcal{X}$ (the raw pile of sand in this case).
• We want to transport it to another distribution $\mathcal{Y}$.
• We want to reduce the cost (be it time or cost) of the transportation, $T:\mathcal{X} \to \mathcal{Y}$.

This problem applies in almost any area of daily life whenever we have to move a distribution rather than a single item. Common areas include computer vision, bioinformatics (especially in single-cell sequencing), and machine learning.