Source-linked AI summary
From Knothe's transport to Brenier's map and a continuation method for optimal transport
Guillaume Carlier, Alfred Galichon, Filippo Santambrogio
TL;DR
The paper asks when the Knothe–Rosenblatt rearrangement can be obtained as a limit of optimal transports. It studies weighted quadratic costs whose coordinate weights become successively dominant, and shows convergence under an additional target condition. The result also motivates a continuation strategy initialized by the Knothe map.
Problem
The paper examines whether weighted quadratic optimal transports converge to the Knothe–Rosenblatt rearrangement and what conditions on the target are needed.
Source: §1 · p. 3Method
The authors study optimal transports for quadratic costs with coordinate weights whose adjacent ratios tend to zero, using the Knothe transport as the limiting map.
Source: §1 · pp. 2–3Results
The weighted transports converge to the Knothe transport when the target satisfies the stated additional condition, which holds if ν is absolutely continuous.
Source: §1 · p. 3Takeaways & Limitations
The Knothe transport provides a cheap initial condition for a continuation method to approximate the optimal transports.
Source: §1 · p. 3A target with atoms can violate the convergence conclusion, as shown by the paper’s counterexample.
Source: §2 · p. 8
Abstract
from arXiv · showhide
A simple procedure to map two probability measures in $\mathbb{R}^d$ is the so-called \emph{Knothe-Rosenblatt rearrangement}, which consists in rearranging monotonically the marginal distributions of the last coordinate, and then the conditional distributions, iteratively. We show that this mapping is the limit of solutions to a class of Monge-Kantorovich mass transportation problems with quadratic costs, with the weights of the coordinates asymptotically dominating one another. This enables us to design a continuation method for numerically solving the optimal transport problem.
1 Introduction
The introduction presents the Knothe–Rosenblatt transport as an iterated sequence of one-dimensional monotone rearrangements and studies it as a limit of weighted quadratic optimal transports. It also motivates a continuation method from this inexpensive map and illustrates the limit with a two-dimensional Gaussian example.
1 Introduction
- The Knothe–Rosenblatt map is built by successively transporting marginals and conditional measures through one-dimensional monotone rearrangements, producing a triangular transport map.Its construction is well-defined when the measures being transported have no atoms.Source: §1 · p. 2
- As adjacent coordinate weights become asymptotically dominant, the weighted optimal transports converge to the Knothe transport provided the target satisfies an additional condition.The target condition is that the relevant one-dimensional marginals and conditional measures have no atoms; it holds when ν is absolutely continuous.Source: §1 · p. 3
- The authors note that the target-side condition is less natural than the source-side condition and that extra assumptions on ν were not previously known to be needed.They state that a counterexample shows convergence can fail without the target condition.Source: §1 · p. 3
- The paper also studies the reverse direction, from the Knothe transport toward Brenier’s map, using the evolution of dual variables to initialize a continuation method.The Knothe map serves as a cheap initial condition for approximating the optimal transports.Source: §1 · pp. 3–4
- In the two-dimensional Gaussian example, the matrix of the weighted optimal transport is the matrix of the Knothe transport.The example is presented as a case with explicit solutions.Source: §1 · p. 4
2 Knothe transport as a limit of quadratic optimal transports
Under the stated source and target assumptions, optimal plans for increasingly separated quadratic coordinate weights converge to the Knothe-Rosenblatt transport plan. When the plans come from maps, the maps converge in L2; the result also extends to suitable smooth strictly convex separable costs.
Theorem 2.1
- Optimal plans for costs with λk(ε)/λk+1(ε) → 0 converge weakly to the Knothe-Rosenblatt transport plan as ε → 0, under (H-source), (H-target), and finite second moments.When the optimal plans are induced by maps, those maps converge in L2(µ).Source: §2 · p. 4
Proof strategy
- The proof identifies the limiting plan coordinate by coordinate, using optimality of the Knothe plan and disintegration to establish equality of successive marginals.Replacing yd by Td(xd) removes a variable; the reverse substitution uses invertibility under the target assumption.Source: §2 · pp. 5, 7
Generalized costs
- The convergence proof also applies to separable costs whose coordinate costs are smooth, strictly convex, and have suitable growth.The corresponding transport maps converge in L2(µ) when the plans are induced by maps.Source: §2 · pp. 4, 8
Counterexample with atoms
- The target-side assumption matters: with an atom in ν2, optimal maps for weights (ε, 1) fail to converge to the Knothe-Rosenblatt map.In the example, the Knothe map is (2(x1 + sgn(x2)), 0), while the optimal map is (x1, 0).Source: §2 · p. 8
Convergence with atoms
- For a purely atomic target, the proof can extend when the target lies on a set where each yi for i < d is a function of yd.This condition holds for finite or countable point sets with distinct yd components.Source: §2 · pp. 8–9
3 An ODE for the dual variables
The paper formulates optimal transport through dual prices and derives an ODE for their evolution as the cost parameter changes. Under the stated regularity and partition conditions, that ODE characterizes the optimal prices, starting from equal-area horizontal strips.
3 An ODE for the dual variables
- For each ε ≥ 0, the quadratic cost uses diagonal weights (ε, 1), and cells assign each point to a minimizing value cε(x, yi) − pi, with p1 = 0 as normalization.Source: §3 · pp. 9–10
- The cell-boundary vertices depend Lipschitzly on prices and ε under the stated geometric bounds, supporting the derivative calculations.The argument uses lower bounds on cell areas and on the relevant boundary angles.Source: §3 · pp. 11–12
- The dual potential has Lipschitz second derivatives with respect to prices and mixed price-parameter derivatives, supporting the ODE’s regularity.The price derivatives are C2,1, and the parameter derivative of the price gradient is Lipschitz.Source: §3 · pp. 12–13
- H1–H3 alone do not ensure eigenvalues stay bounded away from zero, even when the norm of the remaining column is fixed.The paper uses the cell-partition structure to obtain the stronger uniform bound.Source: §3 · p. 15
- A uniform lower bound on the least eigenvalue holds for matrices associated with the cell partitions in the open set O.The proof strengthens the connectivity condition by using the structure of the partitions.Source: §3 · p. 15
- The unique price vector solving the dual problem is characterized by the ODE, initialized with horizontal strips of equal area.The initialization corresponds to ε = 0.Source: §3 · p. 16
4 Numerical results
The paper discretizes the price-evolution ODE with an explicit Euler scheme and tests the continuation method on finite samples. The experiments report small cell-area errors and compare computed partitions and correlation curves with exact results.
4.1 Algorithm
- Each Euler step constructs cells from the prices, solves a positive-definite linear system in N − 1 conjugate-gradient steps, and updates prices by h times the solution.The algorithm starts from the prices specified by Theorem 3.5.Source: §4.1 · pp. 16–17, §4.2 · p. 17
- For sufficiently small h, the Euler algorithm is well-defined and the uniform error between its piecewise-constant prices and the optimal prices is O(h).The convergence claim follows from the Lipschitz property of the ODE’s vector field on O.Source: §4.1 · p. 17
4.2 Numerical experiments
- The experiments compare computed and exact partitions and correlation curves, including the full evolution between Knothe transports using weights (ε, ε−1).The paper reports executions with samples of 5, 10, and 15 points; the correlation curve is described as concave and decreasing with slope −ε where it exists.Source: §4.2 · pp. 18–19
- With 500 discretization steps, the maximal relative cell-area error is 1%, and the run takes 349 seconds on a standard laptop.At 100 steps, the reported relative cell-area error is below 5%.Source: §4.2 · p. 19