Monge Problem between Measures

The goal of this chapter is to pass from finite matching to transport between arbitrary probability laws. The central stakes are to define measures, push-forwards and Monge maps carefully enough that the discrete picture survives, while exposing why deterministic maps can fail to exist. Monge’s original formulation Monge, 1781 and modern treatments Villani, 2003Villani, 2009Santambrogio, 2015Rachev & Rüschendorf, 1998 are the conceptual background for this transition.

The previous chapter handled two sets with the same number of points. To relax this to a more general setting, one needs probability distributions, so that points may carry unequal masses and continuous densities can be treated in the same language as finite clouds.

from pathlib import Path
import sys

from IPython.display import Image as DisplayImage
from IPython.display import display

here = Path.cwd()
myst_dir = None
for candidate in [here, here.parent, here / "myst", here.parent / "myst", here.parent.parent / "myst"]:
    if (candidate / "ot4ml_web.py").exists():
        myst_dir = candidate.resolve()
        sys.path.insert(0, str(myst_dir))
        break

if myst_dir is None:
    raise RuntimeError("Could not locate myst/ot4ml_web.py")

repo_root = myst_dir.parent
thumbnails = repo_root / "notebooks-figures" / "thumbnails"

def show_book_figure(name, width=760):
    display(DisplayImage(filename=str(thumbnails / f"{name}.png"), width=width))

Measures¶

Measures are the language that lets point clouds, densities and singular objects be handled uniformly. We only recall the facts needed later: integration, total variation, densities and probabilistic laws.

Histograms¶

Discrete And Empirical Measures¶

The Dirac mass should be thought of as a unit of mass infinitely concentrated at one location.

An empirical probability distribution is uniform on a point cloud,

In applications, it is useful to manipulate both the positions $x_i$ and the weights $a_i$. Moving the positions is a Lagrangian discretization; changing the weights is an Eulerian one. The Lagrangian view is often more adaptive, but it tends to break convexity.

General Measures¶

We write $\Mm(\X)$ for the finite signed Borel measures on a metric space $(\Xx,d)$. The Borel sets form the smallest $\sigma$-algebra containing the open subsets of $\Xx$, obtained by closing the open sets under complements and countable unions. Unless otherwise stated, all measures are finite.

A Dirac measure is defined by $\delta_x(A)=1$ if $x\in A$ and 0 otherwise. For the discrete measure above,

We denote by $\Mm_+(\X)$ the set of positive finite measures on $\X$ and by $\Mm_+^1(\X)$ the set of probability measures, i.e. positive measures of total mass one.

Polish Metric Spaces¶

Many measure-theoretic statements used later require a mild regularity assumption on the underlying space. The point is not to restrict applications, since Euclidean spaces, complete separable manifolds and separable Hilbert spaces are covered, but to exclude pathological measurable spaces where disintegration, tightness or weak convergence can fail to behave properly.

This assumption already includes genuinely infinite-dimensional spaces. In the Euclidean dynamical formulations used later, the path space

is Polish. Completeness follows because a uniformly Cauchy sequence of continuous paths converges uniformly to a continuous path, and separability follows by approximating paths uniformly by piecewise-linear paths with rational breakpoints and rational values. This example is used later as the state space for laws of trajectories: the endpoint evaluation maps are continuous on $\Ss$, which makes endpoint constraints well behaved for dynamical optimal plans and Schrodinger bridges; see the path-space formulation in Path-Space Formulation and Section Path-Space Schrodinger Problem.

Polish spaces are the natural ambient category for probability measures. Borel probability measures on them are regular, tightness gives compactness criteria, regular conditional probabilities and disintegrations exist under standard assumptions, and Wasserstein spaces remain Polish; see Proposition Proposition: Wasserstein Spaces As Ground Spaces.

Radon Measures¶

A positive Borel measure is Radon if it is inner regular, meaning that the mass of every Borel set is the supremum of the masses of its compact subsets. Every finite Borel measure on a Polish space is Radon. Such a measure integrates measurable functions, and we write the pairing as

For a discrete measure this becomes

Integration against a finite measure on a compact space defines a continuous linear form on the Banach space $(\Cc(\Xx),\|\cdot\|_\infty)$, since $|\int f\d\al|\leq \|f\|_\infty |\al|(\Xx)$. Conversely, the Riesz--Markov--Kakutani representation theorem identifies every continuous linear form on $\Cc(\Xx)$ with integration against a finite signed Radon measure Rudin, 1987Bogachev, 2007. This is the duality $\Mm(\Xx)=\Cc(\Xx)^*$ that later supports convex duality.

Relative Densities¶

On $\RR^d$ the reference $\lambda$ is often Lebesgue measure $\d x$.

Total Variation¶

The norm inherited from the duality $\Mm(\Xx)=\Cc(\Xx)^*$ is the total variation norm.

The absolute value of a signed measure is

where the supremum is over finite or countable measurable partitions of $A$. If $\al=\sum_i a_i\delta_{x_i}$ with distinct atoms, then $|\al|=\sum_i |a_i|\delta_{x_i}$. If $\d\al(x)=\rho(x)\d\lambda(x)$, then $\d|\al|(x)=|\rho(x)|\d\lambda(x)$.

For absolutely continuous measures $\d\al=\rho_\al\d\lambda$ and $\d\be=\rho_\be\d\lambda$,

For two discrete measures, one first recasts both measures as weight vectors on the same finite support. If

let $z_1,\ldots,z_r$ be the distinct points in the union $\{x_i\}_i\cup\{y_j\}_j$ and set

Then $\al=\sum_{k=1}^r a_k\delta_{z_k}$ and $\be=\sum_{k=1}^r b_k\delta_{z_k}$. This convention merges masses located at the same point before comparing the two measures. If the two input supports are already enumerated without repetitions and are disjoint, this simply amounts to taking $(z_k)_k=(x_1,\ldots,x_n,y_1,\ldots,y_m)$ and padding the weights as $a=(\tilde a,0_m)$ and $b=(0_n,\tilde b)$. With this common-support notation,

Probabilistic Interpretation¶

Probability measures represent laws of random variables. Let $(\Omega,\Ff,\PP)$ be an abstract probability space and let $\X$ be Polish. A random variable with values in $\X$ is a measurable map $X:(\Omega,\Ff)\to(\X,\Bb(\X))$, or simply $X:\Omega\to\X$ once the measurable structures are understood. Its law is the Radon probability measure $\al=X_\sharp\PP$ defined by

For every integrable $f$, integration with respect to the law is expectation:

Push Forward¶

Push-forwards encode how maps move mass. This short section is the bridge between deterministic maps and linear operations on measures.

For a measurable map $\T:\X\to\Y$, the push-forward operator $\T_\sharp:\Mm(\X)\to\Mm(\Y)$ records the distribution of image points. It sends a Dirac mass to $\T_\sharp\delta_x=\delta_{\T(x)}$. For discrete measures,

The operation is linear in the input measure, although its definition for a general measure uses inverse images rather than a decomposition into Dirac masses. Moving from $\T$ to $\T_\sharp$ thus linearizes the action of a map at the price of moving from $\Xx$ to the measure space $\Mm(\Xx)$.

Figure Div makes the determinant factor visible. Even when the source density is uniform, nonlinear diffeomorphisms can compress area around one or several centers and expand it elsewhere; the target density is therefore not obtained by the naive composition $\rho_\al\circ\T^{-1}$ alone. The high-density bumps appear exactly where the deformed grid cells have small area.

show_book_figure("monge-jacobian-pushforward-density")

Jacobian determinant in the density push-forward formula. The three panels show smooth diffeomorphisms that strongly compress a uniform source grid around one, three, and five centers. The deformed grid is drawn as a dense red mesh, and the pushed density is shown through black level sets of $\density{\be}(y)=|\det\T'(\T^{-1}y)|^{-1}$. The tighter crop focuses on the bump region, where small grid cells coincide with large values of the pushed density.

Monge’s Formulation¶

Monge’s problem asks for a deterministic map transporting one law onto another while minimizing a prescribed cost. It is geometrically direct, because every source point is assigned one destination, but analytically fragile: the feasible set is non-convex, it can be empty, and a map cannot split mass. These limitations motivate Kantorovich’s relaxation in the next chapter.

Monge Problem¶

Given $\al\in\Mm_+^1(\Xx)$, $\be\in\Mm_+^1(\Yy)$ and a nonnegative measurable cost $c:\Xx\times\Yy\to[0,+\infty]$, the Monge problem is

The constraint $\T_\sharp\al=\be$ means that $\T$ pushes the mass of $\al$ onto $\be$. By convention, the infimum is $+\infty$ when no feasible map exists.

show_book_figure("monge-semidiscrete-maps")

Semi-discrete Monge maps. The red contours show the continuous source density $\al$. The colored regions extend the numerical Laguerre cells over the whole displayed domain, while their masses are computed with respect to $\al$. The circular atoms form the discrete target $\be$. Their colors are tied to horizontal position, with a small random perturbation, and are reused for the cells. Faint segments connect cell barycenters to their images under the piecewise-constant Monge map.

The next figure shows a finite-dimensional instance of this deterministic viewpoint. The source and target measures are empirical color clouds in RGB space, and the map transports colors while leaving pixel positions fixed. Grayscale equalization is one-dimensional, but full palette transfer requires transporting empirical measures in a three-dimensional color space. Early methods used affine statistics or iterated one-dimensional projections Reinhard et al., 2001Pitié et al., 2005; replacing these projections by a three-dimensional OT map gives a more intrinsic palette match Rabin et al., 2011.

Figure Div shows a finite-dimensional instance of this deterministic viewpoint.

show_book_figure("monge-color-transfer-rgb")

Color transfer as a Monge map in RGB space, from a beach photograph to a flower photograph. The top row applies the palette map to the source image; the bottom row shows the empirical color clouds in the RGB cube. Only colors are transported here, not pixel locations.

Monge Distance¶

When $\Xx=\Yy$, $1\leq p<+\infty$ and $c(x,y)=d(x,y)^p$ for a metric $d$, set

The Monge value defines the directed quantity

If the constraint set is empty, then $\widetilde{\Wass}_p(\al,\be)=+\infty$.

The directed value $\widetilde{\Wass}_p$ is useful conceptually, but it is too rigid to be the main distance between measures: it can be infinite and asymmetric. Kantorovich’s formulation remedies both issues by replacing maps with couplings.

Existence And Uniqueness Of The Monge Map¶

This section records the main regimes where Monge’s deterministic formulation becomes well posed. Brenier’s theorem is the central result: for the squared Euclidean cost, absolute continuity of the source restores existence, uniqueness and convex-potential structure.

Brenier’s Theorem¶

Brenier’s theorem Brenier, 1987Brenier, 1991 ensures that in $\RR^d$, for the quadratic cost, absolute continuity of the source is enough for Monge’s problem to have a unique solution. It also gives the decisive structural description: the optimal map is the gradient of a convex potential.

Brenier’s theorem is the higher-dimensional analogue of the one-dimensional monotone rearrangement theorem. In one dimension, the derivative of a convex function is an increasing map; in several dimensions, the corresponding object is the gradient of a convex function. Such gradients are monotone fields:

Radial Measures¶

Radial symmetry gives a useful higher-dimensional case where the Brenier map reduces to a one-dimensional monotone rearrangement. A measure $\al$ on $\RR^d$ is radial if $Q_\sharp\al=\al$ for every orthogonal map $Q$. Such a measure is determined by the law of the radius $\norm{x}$, and the optimal map transports this radius while keeping the angular direction fixed.

If $\al$ is not absolutely continuous, the same radial idea is still useful but has to be interpreted at the level of couplings of the radial variables: atoms on spheres may have to be split, so a Monge map need not exist.

Polar Factorization¶

Brenier’s theorem provides a canonical way to extract the monotone part of a nondegenerate square-integrable map $u:\Omega\to\RR^d$. Its law $\be=u_\sharp\lambda$ records where the mass ends up, but forgets how the points of $\Omega$ were labelled. Brenier’s polar factorization Brenier, 1987Brenier, 1991 separates these effects: a measure-preserving rearrangement changes labels, then the unique convex-gradient map sends the uniform source to the output law.

Absolute continuity is a sufficient form of Brenier’s nondegeneracy hypothesis. Without such a hypothesis, deterministic polar factorization may fail or be nonunique.

Figure Div separates these two factors on a colored grid. Its three panels display $x$, $s(x)$, and $u(x)=(\nabla\phi\circ s)(x)$. The map $s$ swirls the square grid while preserving area, whereas $\nabla\phi$ is a symmetric positive definite affine map and hence the gradient of a convex quadratic potential.

show_book_figure("monge-polar-factorization")

Polar factorization as a relabeling followed by a Brenier map. From left to right, the panels show $x$, $s(x)$ with $s_\sharp\lambda=\lambda$, and $u(x)=\nabla\phi(s(x))$. Here $s$ is generated by the area-preserving flow of a divergence-free Hamiltonian vector field, while the Brenier factor is the symmetric positive definite affine map $\nabla\phi(z)=Bz$. Faint arrows indicate the successive maps.

For linear maps under a Gaussian reference, this reduces to the usual matrix polar decomposition. If $X\sim\Gaussian(0,\Id)$ and $u(x)=Ax$, then $u_\sharp\Gaussian(0,\Id)=\Gaussian(0,AA^\top)$. The Brenier map from $\Gaussian(0,\Id)$ to this Gaussian is $x\mapsto Sx$, where $S=(AA^\top)^{1/2}$ is symmetric positive semidefinite. Hence

When $A$ is invertible, $O=S^{-1}A$ is orthogonal. In the singular square case, $S^\dagger A$ is only a partial isometry and must be extended on its kernel to an orthogonal matrix $O$ before $Ox$ preserves the full standard Gaussian law. The factor $Sx$ is the convex-gradient transport part, whereas $Ox$ is the measure-preserving relabeling.

Displacement Interpolation¶

An optimal map does not only match two endpoint measures; it tells how to draw a path between them. Each particle keeps its identity and travels at constant speed from its initial position to its image.

Figure Div illustrates this displacement geodesic on two non-convex silhouettes, both through representative particle paths and through the evolving transported density.

show_book_figure("monge-shape-mccann-interpolation")

McCann displacement interpolation between a cat silhouette and a heart silhouette. The first row displays a small farthest-point subset of transported particles along $T_t(x)=(1-t)x+tT(x)$. The second row renders kernel-smoothed densities from a denser transported cloud as color images: white means zero density, while high density saturates in the red-to-blue interpolation color of the corresponding time.

Regularity And The Monge-Ampere Equation¶

The previous results identify the optimal map. Regularity theory asks when this map is a classical smooth deformation rather than only an almost-everywhere gradient. For quadratic costs this becomes the regularity theory of the Monge--Ampere equation.

Figure Div illustrates the geometric role of the convexity assumption through a finite-sample stress test rather than a counterexample. A quadratic assignment transports a dense farthest-point sample of the disk to a dense farthest-point sample of a connected non-convex target made of two disks joined by a thin rectangle. The panels show the corresponding empirical McCann interpolation, so the loss of convex target geometry is visible directly along the transported particles.

show_book_figure("monge-caffarelli-nonconvex-map")

Empirical quadratic OT interpolation from a disk to a connected non-convex two-disk domain. A 5200-point farthest-point sample of the disk is matched to a 5200-point farthest-point sample of two disks connected by a thin rectangle. The panels display $(1-t)x_i+tT_N(x_i)$ for the empirical optimal assignment $T_N$. Colors are inherited from the horizontal coordinate of $x_i$ in the initial disk, making the transported material regions visible throughout the interpolation.

For smooth densities, the change-of-variables formula gives the Monge--Ampere equation

With suitable boundary conditions, this characterizes the Brenier potential up to an additive constant among convex solutions. The convexity constraint forces $\det(\nabla^2\phi(x))\geq0$ and is necessary for this fully nonlinear elliptic equation to be well posed.

The following proposition records the infinitesimal form.

Beyond The Quadratic Euclidean Cost¶

The quadratic Euclidean cost is the model case, but optimal-map theory also covers many non-quadratic costs. The key point is to separate three roles: a convexity-like structure gives potentials, a twist condition prevents splitting, and curvature-type conditions give regularity.

$W_p$ Costs¶

The quadratic cost is special because it identifies the optimal map with the Euclidean gradient of an ordinary convex potential. For the Wasserstein cost, normalized as $c(x,y)=\norm{x-y}^p/p$ with $p>1$, the same Monge-map picture survives, but the potential is adapted to the cost. More generally, for $c(x,y)=h(x-y)$ with $h$ smooth and strictly convex, absolute continuity of the source again rules out splitting and yields a unique optimal map. This map is characterized by a $c$-convex potential $f$: at differentiability points of $f$,

For $c(x,y)=\norm{x-y}^p/p$, this gives the explicit relation

Thus the Brenier formula $\T=\nabla\phi$ should be read as the quadratic representative of a broader $c$-convex theory. The Euclidean theory for strictly convex displacement costs is developed in Gangbo--McCann’s work on the geometry of optimal transportation Gangbo & McCann, 1996; see also the general treatment in Villani, 2009.

Squared Geodesic Distance¶

On a Riemannian manifold, the natural analogue of the quadratic Euclidean cost is the squared geodesic distance $c(x,y)=d_M(x,y)^2/2$. The optimal map is no longer written with a vector-space subtraction, but with the exponential map

where $\phi$ is $c$-convex. This is the intrinsic version of the formula $T=x-\nabla\phi$ in normal coordinates. The main additional issues are the cut locus, possible non-uniqueness of minimizing geodesics, and regularity of the exponential map, which is why the Euclidean statement is usually presented first. The Riemannian polar-factorization theorem of McCann McCann, 2001 gives the corresponding optimal-map framework, and these ideas feed into displacement convexity and the general manifold theory of optimal transport McCann, 1997Villani, 2009.

Figure Div makes this intrinsic interpolation explicit on the closed upper hemisphere $M=\mathbb S^2_+=\{x\in\mathbb R^3:\|x\|=1,\ x_3\geq0\}$. Consider two equal-weight empirical measures $\alpha=n^{-1}\sum_i\delta_{x_i}$ and $\beta=n^{-1}\sum_j\delta_{y_j}$ and the intrinsic cost

The Birkhoff--von Neumann theorem gives an optimal permutation coupling $P^\star_{i,\sigma(i)}=1/n$. For a non-antipodal matched pair, let

Each $\gamma_i$ is a constant-speed minimizing spherical geodesic, and $\alpha_t=n^{-1}\sum_i\delta_{\gamma_i(t)}$ is the intrinsic McCann interpolation. The paths stay in the hemisphere because both sine coefficients are nonnegative on $[0,1]$.

show_book_figure("monge-sphere-mccann-interpolation")

Intrinsic McCann interpolation on the upper hemisphere. The thin violet great-circle arcs show the fixed optimal permutation coupling between the hollow red and blue endpoint atoms. The filled atoms follow these arcs at $t=0,1/4,1/2,3/4,1$, with color interpolated from red to blue.

Poincare Disk¶

Negative curvature gives a complementary intrinsic picture. The Poincare disk is

a complete Riemannian manifold of constant curvature -1. Its geodesic distance is

For equal-weight point clouds, the cost $C_{ij}=d_{\mathbb D}(x_i,y_j)^2/2$ again admits an optimal permutation coupling, denoted by $\sigma$. Introduce the hyperboloid lift and Lorentz product

Put $X_i=\iota(x_i)$, $Y_i=\iota(y_{\sigma(i)})$, and $\eta_i=d_{\mathbb D}(x_i,y_{\sigma(i)})$. The constant-speed geodesic is

In disk coordinates, its trace is a Euclidean circle orthogonal to the unit circle, with diameters as the limiting case. Thus $\alpha_t=n^{-1}\sum_i\delta_{\gamma_i(t)}$ is the hyperbolic McCann interpolation shown below. The $\sinh$ coefficients are the negative-curvature counterparts of the $\sin$ coefficients in the spherical formula.

show_book_figure("monge-hyperbolic-mccann-interpolation")

Intrinsic McCann interpolation in the Poincare disk. The black circle is the ideal boundary, the faint grid gives hyperbolic radial and distance coordinates, and the thin violet arcs are the fixed optimal geodesic coupling. Filled atoms move from the hollow red source to the hollow blue target at $t=0,1/4,1/2,3/4,1$.

Twist Condition¶

The first non-degeneracy condition asks that the first-order information at a source point identifies at most one target point. This is the structural hypothesis that turns an optimal relation into a map.

The quadratic cost satisfies twist since $\nabla_x\norm{x-y}^2=2(x-y)$; the bilinear cost $c(x,y)=-\dotp{x}{y}$ satisfies twist since $\nabla_x c(x,y)=-y$; more generally $c(x,y)=h(x-y)$ is twisted when $h$ is smooth strictly convex and $\nabla h$ is injective. On a Riemannian manifold, the squared geodesic cost is twisted locally away from the cut locus. By contrast, a separated cost $a(x)+b(y)$ is never twisted, since $\nabla_x c$ does not see $y$.

Ma--Trudinger--Wang Curvature¶

Twist gives a map, but it does not by itself make this map continuous or smooth. For a general smooth cost, the relevant structural hypothesis is the Ma--Trudinger--Wang (MTW) condition, introduced for a priori estimates of the generated Jacobian equation associated with optimal transport Ma et al., 2005Trudinger & Wang, 2001.

The tensor above is often called the cost-sectional curvature. With this sign convention, it measures how the negative $x$-Hessian of the cost bends when the target point is varied through the dual momentum $p$.

The flat quadratic and bilinear costs have zero MTW curvature, hence satisfy the weak condition. For the squared Riemannian distance, the MTW tensor is a refined curvature condition on the cost: near the diagonal it recovers sectional curvature, negative sectional curvature gives an obstruction, and global regularity also depends on cut-locus and domain-convexity issues. Many smooth strictly convex costs fail MTW, which is why twist is enough for existence of a map but not for regularity.

One-Dimensional Transport And Quantiles¶

Cumulative and quantile functions¶

In one dimension, optimal transport is completely explicit. The cumulative distribution function orders the mass, and the optimal coupling is obtained by matching equal quantile levels. This case is both a computational tool and the template for several linearized constructions used later.

Figure Div follows four smooth laws through these three representations. Each density mode produces a change of slope in the cumulative function, while intervals of low density become steep portions of the quantile function. The aligned quarter-mass guides make the inversion between the last two panels explicit.

show_book_figure("monge-cdf-quantile-mixtures")

Densities, cumulative functions and quantiles for four Gaussian mixtures. Red-to-blue colors identify mixtures with one through four components across all three panels. The cumulative functions integrate the modes into successive increases of mass, while inversion exchanges slowly varying cumulative regions with steep quantile regions. Faint guides mark the same quarter-mass levels in the last two panels.

1D Monge solutions¶

The quantile construction becomes a deterministic Monge map only when the source has no atoms, because the cumulative distribution function can then be used as a genuine change of variable. This gives an explicit one-dimensional Monge solution in the atomless case. If $\al$ has atoms, a deterministic map may fail to realize the same quantile matching because an atom cannot be split; the corresponding relaxed statement is treated in Section Relaxation For Arbitrary Measures, paragraph Kantorovich solution in 1D.

For $p=2$, Bobkov and Ledoux Bobkov & Ledoux, 2019 gave a complementary representation involving only cumulative distribution functions. It gives the same exact value as the quantile formula, but replaces the inverse-CDF step by an integral over CDF values. This is useful when cumulative functions are easier to estimate or aggregate than quantiles. This cumulative formula has recently been used to design data-parallel estimators of sliced Wasserstein distances Vauthier et al., 2026.

The last panel of Figure Div is the one-dimensional specialization of the displacement interpolation introduced above.

show_book_figure("monge-1d-quantile-geodesic")

One-dimensional transport through quantiles. The same two smooth laws are shown as densities, cumulative functions and quantile functions. The last panel displays the displacement interpolation obtained by the linear quantile path $Q_t=(1-t)Q_\alpha+tQ_\beta$, which is the explicit one-dimensional $\Wass_2$ geodesic.

In quantile coordinates, the interpolating measure is characterized by

OT on trees¶

The line is the simplest tree. On a general tree, the order is no longer total, but each edge still defines a cut and hence a cumulative imbalance. This gives an exact formula for the $\Wass_1$ cost associated with the tree geodesic distance. The formula is classical in fast earth-mover computations on tree metrics Ling & Okada, 2007 and is also the mechanism behind tree-sliced Wasserstein distances Le et al., 2019.

For a chain rooted at one end, the sets $V_e$ are rays, so the tree formula is the discrete version of the one-dimensional identity (84). This edgewise cumulative decoupling is specific to the geodesic-distance cost $d_{\mathsf{T}}$, i.e. to $\Wass_1$. For powers $d_{\mathsf{T}}^p$ with $p>1$, the term $\big(\sum_{e\in[x,y]}\ell_e\big)^p$ couples all edges along a path, so the simple sum of absolute subtree imbalances no longer gives the optimal value. The tree structure remains algorithmically useful in a different sense: tree metrics give fast surrogates and embeddings for EMD-type computations on histograms Indyk & Thaper, 2003Andoni et al., 2008Ling & Okada, 2007, and randomized or data-adapted trees lead to tree-sliced Wasserstein distances that trade the exact Euclidean ground metric for much faster one-dimensional/tree computations Le et al., 2019.

The same tree can nevertheless be used as a genuine geodesic space. If $\pi$ is an optimal coupling for the squared tree distance $d_{\mathsf{T}}^2$, the associated displacement interpolation moves each packet of mass $\pi_{ij}$ at constant speed along the unique path from $x_i$ to $x_j$. Figure Div shows this tree analogue of McCann interpolation. The intermediate measures are not necessarily supported on the original vertices: mass may sit inside edges while it travels through the branching structure.

show_book_figure("monge-tree-mccann-interpolation")

McCann interpolation on a finite tree. A quadratic optimal plan is computed between two non-uniform vertex histograms for the squared geodesic distance on the tree. Each transported packet then moves along the unique tree path connecting its source and target vertices. Circle areas encode transported masses, colors interpolate from the source measure $\al$ in red to the target measure $\be$ in blue, and faint colored corridors mark the tree branches carrying transport.

Triangular Rearrangements¶

There is another canonical way to build transport maps in several dimensions: transport one coordinate at a time by conditional one-dimensional quantiles. This construction is not usually cost-optimal, but it gives a deterministic rearrangement under weak assumptions.