Why Moving Points Is Not Enough: Optimal Transport from Monge to Kantorovich

The first time I wrote down Optimal Transport, I thought the problem was about finding a good map.

Move this point here. Move that point there. Minimize the total cost.

That sounds simple, but the word “cost” hides a major choice.

In Optimal Transport, the cost function is not a cosmetic detail. It decides what kind of movement the problem prefers.

For example, suppose we compare two ways of moving books.

One option is to move one book by distance 2.

Another option is to move two books by distance 1.

If the cost grows linearly with distance, these two choices have the same total cost. Moving one book twice as far costs the same as moving two books half as far.

But if the cost is quadratic, the result changes. A long move becomes much more expensive than several short moves. Moving one book by distance 2 now costs 4 units, while moving two books by distance 1 costs only 2 units in total.

So changing the cost function changes the geometry of the transport problem.

A linear cost treats distance proportionally. A quadratic cost strongly punishes long jumps and tends to prefer smoother, more local movement.

This is why Optimal Transport is not just about finding arrows from source to target. It is about choosing what kind of movement the cost function rewards or discourages.

At first glance, Optimal Transport looks like an ordinary optimization problem.

Choose a map. Assign a cost to each movement. Minimize the total cost.

But the most important part is not the minimization symbol. It is the constraint.

Read this as:

Push the source measure μ through the map T, and the result must become the target measure ν.

That line changes the problem.

We are not just deciding where individual points should go. We are asking whether a pointwise rule can reshape an entire distribution.

This is the first conceptual jump in Optimal Transport:

a map acts on points, but transport acts on mass.

This single line says that we are not merely moving points.

We are moving an entire distribution.

That is the first conceptual jump in Optimal Transport.

The Basic Problem: Moving One Distribution Into Another

Suppose we have two probability measures.

The first one is the source distribution, written as μ. The second one is the target distribution, written as ν.

The goal of Optimal Transport is to move the source distribution into the target distribution while paying the smallest possible total cost.

Move this point here. Move that point there. Add up the cost. Find the cheapest arrangement.

In Monge’s formulation, the movement is deterministic. Every source point x is sent to exactly one target point T(x).

So the transport object is a map.

Here, P(X) means the set of probability measures on X. The value c(x, y) tells us how expensive it is to move one unit of mass from x to y.

Monge’s Optimal Transport Problem

The Monge problem asks for the cheapest map T that moves μ into ν.

There are two parts.

First, the map should minimize the average transportation cost over source points sampled from μ.

Second, the map must actually transport the source distribution into the target distribution.

That second condition is the important one.

A map is not valid just because it is cheap. It is valid only if, after applying the map to the source distribution, the result becomes the target distribution.

This condition is written as T#μ = ν.

The objective means:

Average the cost c(x, T(x)) over all source points x sampled according to μ.

So the optimization is looking for the cheapest possible map.

But not every map is allowed. The map must satisfy the push-forward constraint T#μ = ν.

This is what makes T a valid transport map from μ to ν.

What Does T#μ Mean?

The notation T#μ is called the push-forward of μ by T.

The easiest way to read it is:

Sample x from μ. Apply the map T. Then T(x) follows the pushed-forward distribution T#μ.

So T#μ is the distribution produced after applying T to samples from μ.

The constraint T#μ = ν therefore means:

After every source sample is moved through T, the resulting distribution must be exactly the target distribution.

This is the mass-balance condition.

Without it, the optimization would be meaningless. A cost-minimizing map could collapse everything to one cheap location. The push-forward constraint prevents that by forcing the final distribution to match the target.

The Formal Definition of Push-Forward

The formal definition says the same thing, but at the level of sets.

Take any measurable set B inside the target space Y. The transported mass landing inside B should equal the source mass of all points that were mapped into B.

That source set is called the preimage of B under T.

In plain language:

The mass that lands in B after transport equals the mass that originally came from points whose destinations lie in B.

Instead of checking every set B, we can test against a function φ. Integrating φ over the transported distribution is the same as sampling x from μ, applying T, and evaluating φ(T(x)).

This identity is often the cleanest way to understand the push-forward.

The left side integrates over the transported distribution. The right side pushes samples through T first, then evaluates the function.

They are the same because T#μ is exactly the distribution of T(x).

The One-Dimensional Case: Quantile Transport

In one dimension, the Monge problem has a particularly clean structure.

Suppose the source and target both live on the real line. Let Fμ be the cumulative distribution function of the source distribution, and let Fν be the cumulative distribution function of the target distribution.

The source CDF converts a point x into its quantile level.

The inverse target CDF then converts that quantile level into the corresponding target point.

So the optimal one-dimensional transport map sends each source quantile to the matching target quantile.

In words:

The 20th percentile of the source goes to the 20th percentile of the target. The median of the source goes to the median of the target. The 90th percentile of the source goes to the 90th percentile of the target.

This is why one-dimensional transport is often described as quantile matching.

This formula should be read as:

First find the source quantile of x. Then send it to the target point with the same quantile.

Under common regularity assumptions and convex distance costs, this monotone rearrangement gives the optimal Monge map in one dimension.

Simulation: Making T#μ = ν Visible

The push-forward constraint can feel abstract, so let’s make it visible with a one-dimensional simulation.

The experiment is simple.

We sample points from a source distribution μ. We sample points from a target distribution ν. Then we build an empirical transport map by sorting both samples and matching their quantiles.

The smallest source sample goes to the smallest target sample. The median source sample goes to the median target sample. The largest source sample goes to the largest target sample.

This is the finite-sample version of quantile transport.

Here is the minimal Python version:

import numpy as np
import matplotlib.pyplot as plt
np.random.seed(42)
n = 5000
def sample_source(n):
    z = np.random.rand(n)
    x = np.empty(n)
    left = z < 0.55
    x[left] = np.random.normal(-2.0, 0.45, left.sum())
    x[~left] = np.random.normal(0.8, 0.70, (~left).sum())
    return x
def sample_target(n):
    z = np.random.rand(n)
    y = np.empty(n)
    left = z < 0.50
    y[left] = np.random.normal(-0.4, 0.55, left.sum())
    y[~left] = np.random.normal(2.2, 0.45, (~left).sum())
    return y
source = sample_source(n)
target = sample_target(n)
source_sorted = np.sort(source)
target_sorted = np.sort(target)
def empirical_transport_map(x):
    return np.interp(x, source_sorted, target_sorted)
transported = empirical_transport_map(source)
print("Empirical squared cost:", np.mean((source - transported) ** 2))
plt.figure(figsize=(10, 5))
plt.hist(source, bins=80, density=True, alpha=0.45, label="Source μ")
plt.hist(target, bins=80, density=True, alpha=0.45, label="Target ν")
plt.hist(transported, bins=80, density=True, alpha=0.45, label="Pushed-forward source T#μ")
plt.title("Empirical push-forward: T#μ approximately equals ν")
plt.xlabel("Location")
plt.ylabel("Density")
plt.legend()
plt.tight_layout()
plt.show()

The plot should show that the transported source distribution closely matches the target distribution.

That is the numerical meaning of T#μ = ν.

The map T does not merely move individual samples. It changes the whole distribution.

Why Monge Can Fail: A Map Cannot Split Mass

The Monge formulation is elegant, but it has a serious limitation.

A map sends each source point to exactly one target point.

That means one source atom cannot split its mass into multiple target locations.

Consider the simplest possible example.

The source has all mass at 0. The target wants half the mass at -1 and half the mass at 1.

A deterministic map cannot do this.

If T sends 0 somewhere, it has only one value: T(0). So the push-forward of a single atom is still a single atom.

It cannot become two separated atoms.

This is the simplest reason Kantorovich transport is needed.

Monge transport is map-based. But some transportation problems require mass-flow.

Kantorovich Relaxation: Transport Plans Instead of Maps

Kantorovich replaces the deterministic map T with a transport plan γ.

Instead of saying where each source point goes, the plan says how much mass moves from each source location to each target location.

This is a more flexible object.

A map answers:

Where does this point go?

A plan answers:

How much mass moves from here to there?

Because a plan is allowed to split mass, it can solve problems that Monge maps cannot.

The two marginal constraints mean that the plan starts with the correct source distribution and ends with the correct target distribution.

The first marginal is μ. The second marginal is ν.

Unlike a deterministic map, a transport plan can split mass across several destinations.

Simulation: Mass Splitting with a Kantorovich Plan

Now we can return to the example where Monge fails.

The source has all mass at 0. The target wants half the mass at -1 and half the mass at 1.

A Kantorovich plan can represent this directly.

It sends 0.5 units of mass from 0 to -1, and 0.5 units of mass from 0 to 1.

Here is the minimal Python version:

import numpy as np

x = np.array([0.0])
mu = np.array([1.0])

y = np.array([-1.0, 1.0])
nu = np.array([0.5, 0.5])

Gamma = np.array([[0.5, 0.5]])

C = (x[:, None] - y[None, :]) ** 2
total_cost = np.sum(Gamma * C)

print("source marginal:", Gamma.sum(axis=1))
print("target marginal:", Gamma.sum(axis=0))
print("total cost:", total_cost)

The output verifies the two marginal constraints.

The outgoing source mass is 1. The incoming target mass is 0.5 and 0.5.

This is exactly what a deterministic Monge map cannot express.

Discrete Transport as a Matrix Problem

For computational work, the Kantorovich formulation often becomes a matrix problem.

Suppose the source distribution is supported on points x₁, …, xₙ. Suppose the target distribution is supported on points y₁, …, yₘ.

A transport plan becomes a nonnegative matrix Γ.

Each entry Γᵢⱼ tells us how much mass moves from source point xᵢ to target point yⱼ.

The row sums must recover the source masses. The column sums must recover the target masses.

The total cost is the sum of all transported mass multiplied by its movement cost.

In compact matrix form, the constraints are:

This is a linear program.

The matrix Γ is the central computational object.

Monge Versus Kantorovich

The difference can now be summarized cleanly.

Monge transport uses a deterministic map.

Each source point goes to one target point.

Kantorovich transport uses a transport plan.

Each source point can distribute mass across multiple target points.

Monge asks:

Where does each point go?

Kantorovich asks:

How much mass moves between every source-target pair?

That is the conceptual shift.

The Main Idea to Remember

The most important symbol in the handwritten page is T#μ.

Read it as:

Push μ forward through T.

Or more concretely:

Sample x from μ, apply T, and observe the distribution of T(x).

Then the Monge constraint T#μ = ν means:

The transported source distribution must become the target distribution.

This is the first core idea of Optimal Transport.

A map acts on points. A transport map acts on a distribution.

That is why the push-forward notation is not just a technicality. It is the bridge between moving points and moving probability mass.