Optimal transport

Course of Dario Trevisan

We solve the earth movers problem using the POT library.

First, some python initializations.

In [1]:
%matplotlib inline
from matplotlib import rcParams
from ipywidgets import interact, fixed, FloatSlider, RadioButtons
rcParams['figure.figsize'] = (8., 6.)  # Enlarge figure
# A slider for p
sliderd = dict(min=-1., max=2., step=0.05, value=1.1, continuous_update=False)

from earth_movers import EarthMovers1D, EarthMovers2D

1D case

Solve the earth movers problem for 50-position samples.

In [2]:
em1D = EarthMovers1D(50)
interact(em1D.plot_ot, p=FloatSlider(**sliderd), plot_points=fixed(True));

2D case

Solve the earth movers problem for 50-position samples.

In [3]:
em2D = EarthMovers2D(100)
interact(em2D.plot_ot, p=FloatSlider(**sliderd), plot_points=fixed(True));

Solve the earth movers problem for 1000-position samples. The darker the line, the longer the distance.

In [4]:
em2D_large = EarthMovers2D(1000)
interact(em2D_large.plot_ot, p=FloatSlider(**sliderd), plot_points=fixed(False));

Histogram of distance

Plot the histogram of distance for 2000-position samples on the 1D and 2D problems.

In [5]:
def plot_histogram(dimension=2, p=1.1):
    nsim = 2000
    em = EarthMovers1D(nsim) if dimension == 1 else EarthMovers2D(nsim)
    return em.plot_distance_histogram(p, bins=20)

interact(plot_histogram, dimension=RadioButtons(options=[1, 2], value=2), p=FloatSlider(**sliderd));

Todo

  • Uniform random blue and red points on a square #
  • Its optimal mathching, with p=1, n=500 #
  • Histogram of matching length in d=1,2,3 #
  • one dimensional matching for p=1.1 and p=0.9, comparison
  • The scaling algorithm for local optimal matching

PoT: https://pot.readthedocs.io/en/stable/auto_examples/plot_OT_2D_samples.html