What is optimal transport?

Optimal transport refers to the movement of something from one place to another in an efficient manner. Efficiency consists of saving resources and time. The optimal transport, or the Monge-Kantorovich problem, was formalized by the French mathematician Gaspard Monge in 1781.

This problem tends to find an optimal plan to carry materials or transport stuff between two places with ease. One of the very first cases of such usage was in the "Mines and Factories" problem that Monge worked on. The "Mines and Factories" problem tends to find the most optimum transport of iron ores from a mine to a factory. This was later utilized in the "Cow and Artisan"The problem of the waste of time caused by artisans riding to and picking up milk from faraway farms problem.

Example 1

Let's suppose that we have a parking lot with five cars lined together, and there is a robotic arm that can pick them up. An illustration of this is given below:

However, the cars are too congested. The robotic arm is advised to move all the cars up one parking space towards the top of the lot. This is so that if a car enters from the gate, it doesn't have to go the full length to be parked.

There are now two possibilities to move the vehicles:

1. Move "Car 5" 10 km up to the free parking space.

2. Move each car up one parking space, with "Car 1" moving towards the free parking space at the top of the lot.

Both of these are optimal. However, taking the squared Euclidean distanceThis is the distance between the points lying in a plane and then squaring it. In our case, we sum these together to get the final result. makes the second method more efficient.

Example 2

If we now look at a pair of probability distributions and the distance between them, we will understand why optimal transport is so useful.

Let's suppose that we have two probability density functions, $P$ and $Q$. A transportation plan $T$ between $P$ and $Q$ must now fulfill three conditions:

1. $T(P,Q) \ge 0$

2. $\int \int T(P) \:dx\: dy = p(x,y)$

3. $\int \int T(P) T(Q) \:dx\: dy = q(x,y)$

The second condition states that there must be some value assigned to transportation. Meanwhile, the third condition states that the second probability density function $Q$ must be given values as per capacity, no more or less.

If all of these conditions are satisfied, we can write the optimal transport function as follows:

Applications

Some of the applications of optimal transport are as follows:

• Image segmentation

• Image restoration

• Computer vision

• Data analysis

• Machine Learning