optimal transport: one construct, many systems

Optimal transport asks for the cheapest way to rearrange one distribution of mass into another, given a cost for moving a unit of mass from each origin to each destination. Monge posed the problem in 1781 for piles of earth; Kantorovich's On the translocation of masses (published in English in 1958, from his 1942 work) relaxed it into a solvable linear program and, by duality, into a problem about prices, work that also helped found linear programming in economics. Villani's Optimal transport: Old and new is the modern reference. The referent is the minimum-cost coupling between two distributions and the distance it defines, the same construct that reappears as an image metric and a tool for comparing probability distributions.[1][2]

Unit

The minimum total cost to couple one distribution to another

Recovery means

Not applicable

Measured by

Solved as a linear program, or via the dual Kantorovich potentials, for the optimal coupling and its cost

In computer vision the same construct became the earth mover's distance: the minimum total cost of moving earth to turn one image's feature distribution (say its colour or texture histogram) into another's, where shifting mass between dissimilar features costs more. Rubner, Tomasi, and Guibas' 2000 The earth mover's distance as a metric for image retrieval showed it behaves as a true metric and matches human judgements of image similarity better than bin-by-bin comparisons. It is optimal transport realised on image signatures, measured as a retrieval distance rather than an abstract mass-moving cost.[3]

Unit

The least-cost distance between two images' feature distributions

Recovery means

Not applicable

Measured by

Computed as the earth mover's distance between image signatures and used to rank retrieval results

In machine learning the same optimal-transport construct supplies the Wasserstein distance, a way to measure how far apart two probability distributions are by the cheapest plan that morphs one into the other, used to train generative models, align datasets across domains, and compare distributions that barely overlap. Peyré and Cuturi's 2019 Computational optimal transport is the standard account of the fast algorithms that made this practical at scale. It is the identical minimum-cost-coupling idea as Monge and Kantorovich's, here turned into a loss and a geometry over distributions.[4]

Unit

The Wasserstein distance between two probability distributions

Recovery means

Not applicable

Measured by

Estimated with entropic-regularised (Sinkhorn) algorithms as a Wasserstein loss between distributions