Professional website

OT aims at computing a minimal cost transportation between a source probability distribution , and a target distribution . Here we consider the case when those distributions are only available through a finite number of samples, and can be written as

The Kantorovitch formulation of the optimal transport is:

One can also add a regularization term to the optimal transport. In this case the problem becomes

When the optimal transportation plan has been estimated,one can interpolate the distributions from the source to the target. The natural interpolation corresponds to a displacement of the diracs from the source to target distribution

One can also transport the source distribution by expressing the new transported distribution as linear combination of elements from . The transportation of the source samples onto that target samples is computed with:

Those two interpolations have been used in numerous publisations and are illustrated in the following.

We illustrate the OT problem solution and resulting interpolation for a simples 2D dataset in the following. In this particular case the number of source and target samples are equal and the probability masses are all equal to .

On the left, we plot the 2D position of the toy example, when the mouse pointer is on the image, you can see the index of each point. On the right, the corresponding cost matrix , the xias correspond to the index of the samples on the right.

This section illusttrate the two interpolation procedures (diracs and cernter of mass) for two different regularization scheme. When no regularization is used, the solution is a permutation matrix and the mass is tranfered from a unique source sample to a unique target sample. When an entropic regularization is used, the transportation matrix is not sparse anymore and the mass is spread onto several target samples. Use the controls at the end of the page to change the optimal transport regularization and interpolation time .

A complete reference to Optimal Transport has been writtten by C. Villani [1] and is available on the web. The entropic regularization has been proposed in the machine learning community by M. Cuturi [2]. Other regularization such as Laplacian regularization have been proposed in [3].

[1] C. Villani. **Optimal transport: old and new**. Grundlehren der mathematischen
Wissenschaften. Springer, 2009.

[2] M. Cuturi. **Sinkhorn distances: Lightspeed computation of optimal transportation**.
In NIPS, pages 2292–2300. 2013.

[3] S. Ferradans, N. Papadakis, J. Rabin, G. Peyré, and J.-F. Aujol. **Regularized
discrete optimal transport**. In Scale Space and Variational Methods in Computer
Vision, SSVM, pages 428–439, 2013.