summer notes

Learning Notes on Optimal Transport

1. Introduction

OT allows to definemeaningful distancesbetween point clouds (ordatasets), hence isapplicable in most ML settings.

2. Mathematical Formulation

2.1 Monge’s Problem

Monge’s formulation of the OT problem seeks a mapping that transports a mass distributed according to a density to another mass distributed according to a density, minimizing the cost function:

2.2 Kantorovich’s Relaxation

Leonid Kantorovich introduced a relaxed version of Monge’s problem, which is easier to solve with modern computational tools. It transforms the problem into finding a joint distribution over the product space of the sources and the destinations that minimizes:

where ( c(x, y) ) is the cost of transporting mass from ( x ) to ( y ).

Useful Video Screenshot

coupling

3. Computational Methods

3.1 Linear Programming

For discrete distributions, the OT problem can be formulated as a linear program where the objective is to minimize the total transportation cost subject to constraints ensuring that the mass is properly moved from sources to destinations.