The transport problem
A generative model starts from a density that is easy to sample and ends at the density of the data. In this chapter the source is the standard normal on the real line. The target plays the role of the data. It is a mixture of three Gaussians, with weights , means and standard deviations . Time runs from , where the mass is distributed as , to , where it is distributed as . The diffusion sections later in the book run time in the opposite direction. Three objects describe how the mass gets from to . The probability path says where the mass is at time . The velocity field says which way, and how fast, the mass at position moves at time . A particle trajectory follows one sample as the field carries it. This section is about the two endpoints and the ways of pairing them. Fields and trajectories return in the section on dynamic transport. The figure below shows one probability path. Draw and independently and move along the straight line . The density of at each time is a column of the heatmap. Time runs from left to right, and brighter color means more mass. The source density is drawn outside the left edge and the target density outside the right edge. Every transport method in this chapter is drawn in this format, so you can compare them side by side.

Transport maps
The first answer, due to Monge, is a function that sends each source point to a target point. A map transports to when gives . This is written and read as ” pushes forward to ”. In 1D such maps are easy to build from cumulative distribution functions. Write for the CDF of and for the CDF of . If , then is uniform on . Applying the quantile function to a uniform variable produces a sample of . So the increasing map transports to . If is uniform, so is . The decreasing map therefore also transports to . The mixture CDF has no elementary inverse, so is computed by searching for the root of . The largest error of this inversion over a grid of quantile levels is printed below. Both maps used in this section rely on it.

Monge’s problem
Monge asked for the map with the smallest transport cost. With the squared distance as the cost of moving one unit of mass, the problem is The integral is the average of over . Two pairs of points show why the increasing map is cheaper. Take two source points of equal mass and two targets . The ordered pairing sends and . The crossed pairing sends and . The squares cancel in the difference of the two costs, which leaves The crossed pairing always costs more. A map that is not increasing sends some pair to , and swapping the targets of small intervals of mass around and lowers the cost. So in 1D the cheapest map is the increasing one, (Santambrogio, 2015). For source points and target points of equal mass, the same argument says that you solve the discrete problem by sorting both lists and pairing them in order. The code below computes the cost of both maps on the mixture and checks the two-point identity on random points.PI, MU and SIGMA at the top of this section, the checks above still apply.
Couplings
A map sends each source point to exactly one place. Sometimes mass has to split. Take one source point with mass 1 and two target points and with mass each. Any map sends the whole source point to a single target, so no map transports this source to this target. Kantorovich replaced maps with couplings. A coupling is a joint distribution of a pair whose first marginal is and whose second marginal is . It says how much mass at goes to , and the mass at one may spread over several . The cost of a coupling is , and Kantorovich’s problem is to minimize this cost over all couplings (Santambrogio, 2015; Peyré & Cuturi, 2018). A coupling need not have a density. The coupling of a map puts all its mass on the graph , so maps are a special case. On finitely many points a coupling is a matrix with , row sums equal to the source masses and column sums equal to the target masses . Its cost is with . Both the cost and the constraints are linear in , so the problem is a linear program. For the split example the only coupling sends half of the mass to each target, and the solver finds it.
The Wasserstein distance
The cost of the optimal coupling is the squared Wasserstein distance, where the minimum runs over all couplings of and . In 1D the optimal coupling pairs equal quantile levels: the point at level of goes to the point at level of . Substituting in the cost of the increasing map gives the squared distance between the two quantile functions (Peyré & Cuturi, 2018). The code below evaluates this integral and compares it with the linear program as the grid is refined.Optional: entropic transport and Sinkhorn iterations
This subsection is outside the main line of the chapter. You can skip to Brenier’s theorem below. The linear program grows quickly with the number of points: a grid of points has unknowns. Cuturi’s remedy was to add an entropy term to the cost (Cuturi, 2013). For , solve over the same matrices with row sums and column sums . The solution has the form with . Sinkhorn’s algorithm finds the scalings by alternating between the two marginal constraints: where divides entry by entry. For small the entries of underflow, so the iteration below runs on the logarithms of the scalings.
Brenier’s theorem
In more than one dimension there is no ordering to sort by, but the answer has the same structure. For the squared distance cost and a source with a density, Brenier’s theorem states that the optimal coupling is given by a map, that this map is unique, and that it is the gradient of a convex function (Santambrogio, 2015; Peyré & Cuturi, 2018). In 1D an increasing function is the derivative of a convex function, so the quantile map is the Brenier map of this section. In higher dimensions the theorem guarantees the map but gives no formula for it, and it has to be computed numerically. Key references: (Peyré & Cuturi, 2018; Santambrogio, 2015; Cuturi, 2013)References
- Cuturi, M. (2013). Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances. arXiv [stat.ML]. DOI
- Peyré, G., Cuturi, M. (2018). Computational Optimal Transport. arXiv [stat.ML]. DOI
- Santambrogio, F. (2015). Optimal transport for applied mathematicians – calculus of variations, PDEs and modeling.
Found an error on this page? Report an issue.

