# Optimal Transport

Optimal transport is the general problem of moving one distribution of mass to another as efficiently as possible.

This is a VERY old problem.

OT for ML: https://remi.flamary.com/cours/tuto_otml.html

### Solving optimal transport

https://pythonot.github.io/quickstart.html?highlight=geomloss The optimal transport problem between discrete distributions is often expressed as

$γ_{∗}=argmin_{γ∈R_{+}}∑_{i,j}γ_{i,j}M_{i,j}$ $s.t.γ1=a;γ_{T}1=b;γ≥0$ where:

- $M∈R_{+}$ is the metric cost matrix defining the cost to move mass from bin $a_{i}$ to bin $b_{j}$.
- $a$ and $b$ are histograms on the simplex (positive, sum to 1) that represent the weights of each samples in the source and target distributions.

This Python library seems to explain:

- https://pythonot.github.io/master/index.html
- A memory efficient implement of Sinkhorn is found in Geomloss

For example, think of using a pile of dirt to fill a hole of the same volume, so as to minimize the average distance moved.

The Earth Mover’s Distance computes the optimal transport.

Also see Sinkhorn Distance

I also see it as Gradient Flow, but I definitely don’t think it’s the same thing.