Discrete Optimal Transport

From Optimal Transport Wiki
Jump to navigation Jump to search

If the measures are both finite convex combinations of Dirac masses, the Kantorovich and Monge problems may be stated as linear programs[1], and solved using classical methods[2]. This insight may be used to approximate the Wasserstein distances between general measures, by first discretizing the source and target with a known level of accuracy (a difficult problem!), then computing the cost between the discrete measures.

Statement of the Discrete Problems

We suppose that and (assuming the weights and are all positive, the and are distinct, and ). Then any transport plan for scalars (if it charged anything other than the product of the supports of and , it would not have the correct marginals). For notation, set , , , (or more generally for generic cost functions), and denote by the vector of all ones of dimension . Essentially, we are replacing the space with and passing from measures and functions to vectors and matrices.

Primal Problems

With all this notation, we can say the collection of transport plans is analogous to

and the analogue of the (original) Kantorovich Problem is
(where is just shorthand for , an inner product on matrices).

We could define a transport map as a function , but it will be more convenient to define it as a matrix in , subject to constraints (erasing the difference between a transport map and the transport plan it defines). We can say the collection of transport maps is

That is, a transport map corresponds to a plan which does not split mass, but instead sends all mass at to the such that (since and correspond to probability measures—that is, —this is unique for a given ). Then the analogue of the Monge Problem is
As in the general case, this may fail to exist; in fact, may be empty, for example if .

Dual Problem

This also has an analogue.

Useful Combinatorial Structure

The set is a closed polytope in , and since (resp. ) is a linear functional bounded below by zero on , it is quite classical[3] (perhaps taking a compact set formed by restricting to those plans with for some fixed ) that its minimum is obtained at an extreme point.


Simplex Algorithm

This is also very classical.

Improved Algorithms

There are other, improved methods with their own articles, like the Auction Algorithm and Sinkhorn's Algorithm. Perhaps short descriptions/groupings of them should be put on this page to collect the information?