这是用户在 2024-5-3 22:39 为 https://ar5iv.labs.arxiv.org/html/1710.02634?_immersive_translate_auto_translate=1 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?

Notions of optimal transport theory and how to implement them on a computer
最优输送理论的概念及如何在计算机上实施它们

Bruno Lévy and Erica Schwindt
Bruno Lévy 和 Erica Schwindt
Abstract 摘要

This article gives an introduction to optimal transport, a mathematical theory that makes it possible to measure distances between functions (or distances between more general objects), to interpolate between objects or to enforce mass/volume conservation in certain computational physics simulations. Optimal transport is a rich scientific domain, with active research communities, both on its theoretical aspects and on more applicative considerations, such as geometry processing and machine learning. This article aims at explaining the main principles behind the theory of optimal transport, introduce the different involved notions, and more importantly, how they relate, to let the reader grasp an intuition of the elegant theory that structures them. Then we will consider a specific setting, called semi-discrete, where a continuous function is transported to a discrete sum of Dirac masses. Studying this specific setting naturally leads to an efficient computational algorithm, that uses classical notions of computational geometry, such as a generalization of Voronoi diagrams called Laguerre diagrams.
本文介绍了最优输运的数学理论,该理论使得能够衡量函数之间的距离(或更一般对象之间的距离),在对象之间进行插值,或在某些计算物理模拟中强制执行质量/体积保守性。最优输运是一个丰富的科学领域,拥有积极的研究社区,既包括其理论方面,也包括更实际的考虑,如几何处理和机器学习。本文旨在解释最优输运理论背后的主要原则,介绍涉及的不同概念,更重要的是它们之间的关系,以便读者把握构建它们的优雅理论的直觉。然后我们将考虑一个称为半离散的特定设置,其中连续函数被输送到 Dirac 质量的离散总和。研究这个特定设置自然地导致了一种高效的计算算法,该算法使用计算几何的经典概念,如称为拉盖尔图的 Voronoi 图的一般化。

1 Introduction 1 介绍

This article presents an introduction to optimal transport. It summarizes and complements a series of conferences given by B. Lévy between 2014 and 2017. The presentations stays at an elementary level, that corresponds to a computer scientist’s vision of the problem. In the article, we stick to using standard notions of analysis (functions, integrals) and linear algebra (vectors, matrices), and give an intuition of the notion of measure. The main objective of the presentation is to understand the overall structure of the reasoning 111Teach principles, not equations. [R. Feynman]
教授原理,而非方程式。 [R. Feynman]

本文介绍了最优输运。 它总结和补充了 B. Lévy 在 2014 年至 2017 年间举办的一系列会议。 演示在一个初等水平上停留,对应于计算机科学家对问题的看法。 在本文中,我们坚持使用分析的标准概念(函数,积分)和线性代数(向量,矩阵),并提供关于测度概念的直觉。 这篇演讲的主要目标是理解推理的整体结构 1
, and to follow a continuous path from the theory to an efficient algorithm that can be implemented in a computer.
以及从理论到有效算法的连续路径,这些算法可以在计算机中实现。

Optimal transport, initially studied by Monge, [Mon84], is a very general mathematical framework that can be used to model a wide class of application domains. In particular, it is a natural formulation for several fundamental questions in computer graphics [Mém11, Mér11, BvdPPH11], because it makes it possible to define new ways of comparing functions, of measuring distances between functions and interpolating between two (or more) functions :
最优输运最初由蒙日[Monge,Mon84]研究,是一个非常通用的数学框架,可以用来模拟广泛的应用领域。特别是,它是计算机图形学中几个基本问题的自然表述[Mém11,Mér11,BvdPPH11],因为它可以定义比较函数、测量函数之间距离以及插值两个(或多个)函数的新方法:

Refer to caption

Figure 1: Comparing functions: one would like to say that f1subscript𝑓1f_{1} is nearer to f2subscript𝑓2f_{2} than f3subscript𝑓3f_{3}, but the classical L2subscript𝐿2L_{2} norm “does not see” that the graph of f2subscript𝑓2f_{2} corresponds to the graph of f1subscript𝑓1f_{1} slightly shifted along the x𝑥x axis.
图 1:比较函数:人们希望说 f1subscript𝑓1f_{1}f3subscript𝑓3f_{3} 更靠近 f2subscript𝑓2f_{2} ,但是经典的 L2subscript𝐿2L_{2} 范数“看不到” f2subscript𝑓2f_{2} 的图与 f1subscript𝑓1f_{1} 的图沿 x𝑥x 轴稍微移动的对应关系。

Comparing functions 比较函数

Consider the functions f1subscript𝑓1f_{1}, f2subscript𝑓2f_{2} and f3subscript𝑓3f_{3} in Figure 1. Here we have chosen a function f1subscript𝑓1f_{1} with a wildly oscillating graph, and a function f2subscript𝑓2f_{2} obtained by translating the graph of f1subscript𝑓1f_{1} along the x𝑥x axis. The function f3subscript𝑓3f_{3} corresponds to the mean value of f1subscript𝑓1f_{1} (or f2subscript𝑓2f_{2}). If one measures the relative distances between these functions using the classical L2subscript𝐿2L_{2} norm, that is dL2(f,g)=(f(x)g(x))2𝑑xsubscript𝑑subscript𝐿2𝑓𝑔superscript𝑓𝑥𝑔𝑥2differential-d𝑥d_{L_{2}}(f,g)=\int(f(x)-g(x))^{2}dx, one will find that f1subscript𝑓1f_{1} is nearer to f3subscript𝑓3f_{3} than f2subscript𝑓2f_{2}. Optimal transport makes it possible to define a distance that will take into account that the graph of f2subscript𝑓2f_{2} can be obtained from f1subscript𝑓1f_{1} through a translation (like here), or through a deformation of the graph of f1subscript𝑓1f_{1}. From the point of view of this new distance, the function f1subscript𝑓1f_{1} will be nearer to f2subscript𝑓2f_{2} than to f3subscript𝑓3f_{3}.
考虑图 1 中的函数 f1subscript𝑓1f_{1}f2subscript𝑓2f_{2}f3subscript𝑓3f_{3} 。这里我们选择了一个图形急剧振荡的函数 f1subscript𝑓1f_{1} ,以及一个通过沿 x𝑥x 轴平移 f1subscript𝑓1f_{1} 的图形获得的函数 f2subscript𝑓2f_{2} 。函数 f3subscript𝑓3f_{3} 对应于 f1subscript𝑓1f_{1} (或 f2subscript𝑓2f_{2} )的平均值。如果使用经典的 L2subscript𝐿2L_{2} 范数测量这些函数之间的相对距离,即 dL2(f,g)=(f(x)g(x))2𝑑xsubscript𝑑subscript𝐿2𝑓𝑔superscript𝑓𝑥𝑔𝑥2differential-d𝑥d_{L_{2}}(f,g)=\int(f(x)-g(x))^{2}dx ,就会发现 f1subscript𝑓1f_{1}f2subscript𝑓2f_{2} 更接近 f3subscript𝑓3f_{3} 。最优输运使得可能定义一个考虑到 f2subscript𝑓2f_{2} 的图形可以通过平移(就像这里一样)或通过 f1subscript𝑓1f_{1} 的图形的变形从 f1subscript𝑓1f_{1} 获得。从这种新距离的视角来看,函数 f1subscript𝑓1f_{1} 将比 f3subscript𝑓3f_{3} 更接近 f2subscript𝑓2f_{2}

Refer to caption


Figure 2: Interpolating between two functions: linear interpolation makes a hump disappear while the other hump appears; displacement interpolation, stemming from optimal transport, will displace the hump as expected.
图 2:在两个函数之间插值:线性插值使一个驼峰消失,而另一个驼峰出现;来自最优输运的位移插值将按预期移动驼峰。

Interpolating between functions:
在函数之间插值:

Now consider the functions u𝑢u and v𝑣v in Figure 2. Here we suppose that u𝑢u corresponds to a certain physical quantity measured at an initial time t=0𝑡0t=0 and that v𝑣v corresponds to the same phenomenon measured at a final time t=1𝑡1t=1. The problem that we consider now consists in reconstructing what happened between t=0𝑡0t=0 and t=1𝑡1t=1. If we use linear interpolation (Figure 2, top-right), we will see the left hump progressively disappearing while the right hump progressively appears, which is not very realistic if the functions represent for instance a propagating wave. Optimal transport makes it possible to define another type of interpolation (Mc. Cann’s displacement interpolation, Figure 2, bottom-right), that will progressively displace and morph the graph of u𝑢u into the graph of v𝑣v.
现在考虑图 2 中的函数 u𝑢uv𝑣v 。在这里,我们假设 u𝑢u 对应于在初始时间 t=0𝑡0t=0 测量的某个物理量,而 v𝑣v 对应于在最终时间 t=1𝑡1t=1 测量的同一现象。我们现在考虑的问题是重建 t=0𝑡0t=0t=1𝑡1t=1 之间发生的事情。如果我们使用线性插值(图 2,右上角),我们会看到左侧的小丘逐渐消失,而右侧的小丘逐渐出现,这对于函数例如代表传播波的情况并不是很现实的。最优输运使得可以定义另一种类型的插值(Mc. Cann 的位移插值,图 2,右下角),这将逐渐将 u𝑢u 的图形位移和变形为 v𝑣v 的图形。

Optimal transport makes it possible to define a geometry of a space of functions222or more general objects, called probability measures, more on this later.
或更通用的对象,称为概率测度,以后会详细介绍。

最优输运使得可以定义函数空间的几何 2
, and thus gives a definition of distance in this space, as well as means of interpolating between different functions, and in general, defining the barycenter of a weighted family of functions, in a very general context. Thus, optimal transport appears as a fundamental tool in many applied domains. In computer graphics, applications were proposed, to compare and interpolate objects of diverse natures [BvdPPH11], to generate lenses that can concentrate light to form caustics in a prescribed manner [MMT17, STTP14]. Moreover, optimal transport defines new tools that can be used to discretize Partial Differential Equations, and define new numerical solution mechanisms [BCMO14]. This type of numerical solution mechanism can be used to simulate for instance fluids [GM17], with spectacular applications and results in computer graphics [dGWH+15].
,从而为该空间提供了距离的定义,以及在不同函数之间插值的手段,通常在非常一般的情况下定义加权函数族的重心。因此,最优输运在许多应用领域中都是一种基本工具。在计算机图形学中,有一些应用被提出,用于比较和插值不同性质的对象[BvdPPH11],生成可以聚焦光线以预定方式形成焦散光斑的透镜[MMT17, STTP14]。此外,最优输运定义了可以用来离散化偏微分方程并定义新的数值解机制[BCMO14]的新工具。这种数值解机制可以用来模拟例如流体[GM17],在计算机图形学中具有引人注目的应用和结果[dGWH + 15]。

The two sections that follow are partly inspired by [Vil09], [San14], [Caf03] and [AG13], but stay at an elementary level. Here the main goal is to give an intuition of the different concepts, and more importantly an idea of the way the relate together. Finally we will see how they can be directly used to design a computational algorithm with very good performance, that can be used in practice in several application domains.
以下两个部分在一定程度上受到[Vil09],[San14],[Caf03]和[AG13]的启发,但保持在初级水平。 在这里,主要目标是给出对不同概念的直觉,更重要的是对它们之间的关系的一种理解。 最后,我们将看到如何直接使用它们来设计一个性能非常优异的计算算法,该算法可以在实践中在多个应用领域中使用。

Refer to caption

Figure 3: Given two terrains defined by their height functions u𝑢u and v𝑣v, symbolized here as gray levels, Monge’s problem consists in transforming one terrain into the other one by moving matter through an application T𝑇T. This application needs to satisfy a mass conservation constraint.
图 3:假设有两个由高度函数定义的地形 u𝑢uv𝑣v ,这里表示为灰度级别,Monge 的问题在于通过将物质通过应用 T𝑇T 从一个地形转换为另一个地形。 这种应用需要满足质量守恒约束。

2 Monge’s problem 蒙日问题

The initial optimal transport problem was first introduced and studied by Monge, right before the French revolution [Mon84]. We first give an intuitive idea of the problem, then quickly introduce the notion of measure, that is necessary to formally state the problem in its most general form and to analyze it.
最初的最优输运问题是在法国大革命前由蒙日首次引入和研究的[Mon84]。我们首先直观地介绍问题的概念,然后快速引入测度的概念,这对于在其最一般形式下正式陈述问题并分析问题是必要的。

2.1 Intuition 直觉

Monge’s initial motivation to study this problem was very practical: supposing you have an army of workmen, how can you transform a terrain with an initial landscape into a given desired target landscape, while minimizing the total amount of work ?
蒙日最初研究这个问题的动机非常实际:假设你有一支工人队,如何将初始地形转变为目标地形,同时最大限度地减少总工作量?

Monge’s initial problem statement was as follows:
蒙日最初的问题陈述如下:

infT:XXXc(x,T(x))u(x)𝑑x subject to: BX,T1(B)u(x)𝑑x=Bv(x)𝑑xsubscriptinfimum:𝑇𝑋𝑋subscript𝑋𝑐𝑥𝑇𝑥𝑢𝑥differential-d𝑥 subject to: formulae-sequencefor-all𝐵𝑋subscriptsuperscript𝑇1𝐵𝑢𝑥differential-d𝑥subscript𝐵𝑣𝑥differential-d𝑥\begin{array}[]{l}\inf\limits_{T:X\rightarrow X}\int\limits_{X}c(x,T(x))u(x)dx\\[17.07164pt] \mbox{\ \ \ \ subject to: }\\[17.07164pt] \forall B\subset X,\int\limits_{T^{-1}(B)}u(x)dx=\int\limits_{B}v(x)dx\end{array}

where X𝑋X is a subset of 2superscript2{\mathbb{R}}^{2}, u𝑢u and v𝑣v are two positive functions defined on X𝑋X and such that Xu(x)𝑑xsubscript𝑋𝑢𝑥differential-d𝑥\int_{X}u(x)dx = Yv(x)𝑑xsubscript𝑌𝑣𝑥differential-d𝑥\int_{Y}v(x)dx, and c(,)𝑐c(\cdot,\cdot) is a convex distance (the Euclidean distance in Monge’s initial problem statement).
其中 X𝑋X2superscript2{\mathbb{R}}^{2} 的子集, u𝑢uv𝑣v 是在 X𝑋X 上定义的两个正函数,使得 Xu(x)𝑑xsubscript𝑋𝑢𝑥differential-d𝑥\int_{X}u(x)dx = Yv(x)𝑑xsubscript𝑌𝑣𝑥differential-d𝑥\int_{Y}v(x)dxc(,)𝑐c(\cdot,\cdot) 是一个凸距离(蒙日初始问题陈述中的欧几里得距离)。

The functions u𝑢u and v𝑣v represent the height of the current landscape and the height of the target landscape respectively (symbolized as gray levels in Figure 3). The problem consists in finding (if it exists) a function T𝑇T from X𝑋X to X𝑋X that transforms the current landscape u𝑢u into the desired one v𝑣v, while minimizing the product of the amount of transported earth u(x)𝑢𝑥u(x) with the distance c(x,T(x))𝑐𝑥𝑇𝑥c(x,T(x)) to which it was transported. Clearly, the amount of earth is conserved during transport, thus the total quantity of earth should be the same in the source and target landscapes (the integrals of u𝑢u and v𝑣v over X𝑋X should coincide). This global matter conservation constraint needs to be completed with a local one. The local matter conservation constraint enforces that in the target landscape, the quantity of earth received in any subset B𝐵B of X𝑋X corresponds to what was transported here, that is the quantity of earth initially present in the pre-image T1(B)superscript𝑇1𝐵T^{-1}(B) of B𝐵B under T𝑇T. Without this constraint, one could locally create matter in some places and annihilate matter in other places in a counterbalancing way. A map T𝑇T that satisfies the local mass conservation constraint is called a transport map.
函数 u𝑢uv𝑣v 分别表示当前地貌的高度和目标地貌的高度(在图 3 中以灰度级表示)。问题在于找到(如果存在)一个从 X𝑋XX𝑋X 的函数 T𝑇T ,将当前地貌 u𝑢u 转变为期望的地貌 v𝑣v ,同时最小化通过运输的土壤数量 u(x)𝑢𝑥u(x) 与其运输距离 c(x,T(x))𝑐𝑥𝑇𝑥c(x,T(x)) 的乘积。显然,土壤的数量在运输过程中是不变的,因此源地貌和目标地貌中土壤的总量应当相同(在 X𝑋Xu𝑢uv𝑣v 的积分应当一致)。这一全局物质守恒约束需要进一步补充一条局部物质守恒约束。局部物质守恒约束要求在目标地貌中,任意子集 B𝐵B 所接收的土壤数量应与运输到这里的土壤数量对应,也就是最初存在于 T𝑇T 下的 B𝐵B 的前像中土壤数量应当一致。如果没有这一约束,人们可以在一些地方本地创造物质,并在其他地方以相等的方式消除物质。 符合局部质量守恒约束的地图称为输运地图。

Refer to caption

Figure 4: Transport from a function (gray levels) to a discrete point-set (blue disks).
图 4:从函数(灰度级)传输到离散点集(蓝色圆盘)。

2.2 Monge’s problem with measures
2.2 蒙日问题与度量

We now suppose that instead of a “target landscape”, we wish to transport earth (or a resource) towards a set of points (that will be denoted by Y𝑌Y for now on), that represent for instance a set of factories that exploit a resource, see Figure 4. Each factory wishes to receive a certain quantity of resource (depending for instance of the number of potential customers around the factory). Thus, the function v𝑣v that represents the “target landscape” is replaced with a function on a finite set of points. However, if a function v𝑣v is zero everywhere except on a finite set of points, then its integral over X𝑋X is also zero. This is a problem, because for instance one cannot properly express the mass conservation constraint. For this reason, the notion of function is not rich enough for representing this configuration. One can use instead measures (more on this below), and associate with each factory a Dirac mass weighted by the quantity of resource to be transported to the factory.
现在我们假设,我们不是想要将土地(或资源)运输到“目标景观”,而是希望将土地(或资源)运输到一组点(暂时表示为 Y𝑌Y )。这些点例如代表一组开采资源的工厂,参见图 4。每个工厂都希望获得一定数量的资源(取决于工厂周围潜在客户的数量)。因此,表示“目标景观”的函数 v𝑣v 被替换为一组有限点上的函数。然而,如果函数 v𝑣v 在除一组有限点外的所有地方均为零,则其在 X𝑋X 上的积分也为零。这是一个问题,因为例如不能正确表达质量守恒约束。因此,函数的概念不足以表示这种配置。可以改用度量(下文详述),并将每个工厂与要运往工厂的资源数量加权的 Dirac 质量相关联。

From now on, we will use measures μ𝜇\mu and ν𝜈\nu to represent the “current landscape” and the “target landscape”. These measures are supported by sets X𝑋X and Y𝑌Y, that may be different sets (in the present example, X𝑋X is a subset of 2superscript2{\mathbb{R}}^{2} and Y𝑌Y is a discrete set of points). Using measures instead of function not only makes it possible to study our “transport to discrete set of factories” problem, but also it can be used to formalize computer objects (meshes) and directly leads to a computational algorithm. This algorithm is very elegant because it is a verbatim computer translation of the mathematical theory (see §7.6). In this particular setting, translating from the mathematical language to the algorithmic setting does not require to make any approximation. This is made possible by the generality of the notion of measure.
从现在开始,我们将使用测度 μ𝜇\muν𝜈\nu 来表示“当前景观”和“目标景观”。这些测度由集合 X𝑋XY𝑌Y 支持,这些集合可能是不同的(在当前示例中, X𝑋X2superscript2{\mathbb{R}}^{2} 的子集, Y𝑌Y 是一组离散的点)。使用测度而不是函数不仅可以研究我们的“运输到离散工厂集合”的问题,还可以用来形式化计算机对象(网格),并直接导致一个计算算法。这个算法非常优雅,因为它是数学理论的逐字计算机转换(见第 7.6 节)。在这种特定情境中,将数学语言转化为算法设置不需要进行任何近似。这是由测度概念的一般性所实现的。

The reader who wishes to learn more on measure theory may refer to the textbook [Tao11]. To keep the length of this article reasonable, we will not give here the formal definition of a measure. In our context, one can think of a measure as a “function” that can be only queried using integrals and that can be “concentrated” on very small sets (points). The following table can be used to intuitively translate from the “language of functions” to the “language of measures” :
希望学习测度论的读者可以参考教材[Tao11]。为了保持本文的长度合理,我们不会在此处给出测度的正式定义。在我们的语境中,可以将测度看作是一个只能通过积分查询并能“聚集”在非常小的集合(点)上的“函数”。以下表格可用于直观地从“函数的语言”翻译成“测度的语言”:

Function uMeasure μ Bu(x)𝑑xμ(B) or B𝑑μBf(x)u(x)𝑑xBf(x)𝑑μu(x)N/Amissing-subexpressionmissing-subexpressionFunction uMeasure μ missing-subexpressionmissing-subexpressionsubscript𝐵𝑢𝑥differential-d𝑥𝜇𝐵 or subscript𝐵differential-d𝜇subscript𝐵𝑓𝑥𝑢𝑥differential-d𝑥subscript𝐵𝑓𝑥differential-d𝜇𝑢𝑥𝑁𝐴\begin{array}[]{|c|c|}\hline\cr\mbox{Function $u$}&\mbox{Measure $\mu$ }\\[5.69054pt] \hline\cr\int_{B}u(x)dx&\mu(B)\mbox{ or }\int_{B}d\mu\\[5.69054pt] \int_{B}f(x)u(x)dx&\int_{B}f(x)d\mu\\[5.69054pt] u(x)&N/A\\ \hline\cr\end{array}

(Note: in contrast with functions, measures cannot be evaluated at a point, they can be only integrated over domains).
(注意:与函数相对应,测度不能在一个点被评估,它们只能在域上被积分)。

In its version with measures, Monge’s problem can be stated as follows:
在具有测度的版本中,蒙日问题可以陈述如下:

infT:XYXc(x,T(x))𝑑μ subject to ν=Tμsubscriptinfimum:𝑇𝑋𝑌subscript𝑋𝑐𝑥𝑇𝑥differential-d𝜇 subject to 𝜈𝑇𝜇\begin{array}[]{l}\inf\limits_{T:X\rightarrow Y}\int\limits_{X}c(x,T(x))d\mu\ \mbox{ subject to }\ \nu=T\sharp\mu\end{array} (M)

where X𝑋X and Y𝑌Y are Borel sets (that is, sets that can be measured), μ𝜇\mu and ν𝜈\nu are two measures on X𝑋X and Y𝑌Y respectively such that μ(X)=ν(Y)𝜇𝑋𝜈𝑌\mu(X)=\nu(Y) and c(,)𝑐c(\cdot,\cdot) is a convex distance. The constraint ν=Tμ𝜈𝑇𝜇\nu=T\sharp\mu, that reads “T𝑇T pushes μ𝜇\mu onto ν𝜈\nu” corresponds to the local mass conservation constraint. Given a measure μ𝜇\mu on X𝑋X and a map T𝑇T from X𝑋X to Y𝑌Y, the measure Tμ𝑇𝜇T\sharp\mu on Y𝑌Y, called “the pushforward of μ𝜇\mu by T𝑇T”, is such that Tμ(B)=μ(T1(B))𝑇𝜇𝐵𝜇superscript𝑇1𝐵T\sharp\mu(B)=\mu(T^{-1}(B)) for all Borel set BY𝐵𝑌B\subset Y. Thus, the local mass conservation constraint means that μ(T1(B))=ν(B)𝜇superscript𝑇1𝐵𝜈𝐵\mu(T^{-1}(B))=\nu(B) for all Borel set B𝐵B \subset Y𝑌Y.
其中 X𝑋XY𝑌Y 是 Borel 集合(即可以被测量的集合), μ𝜇\muν𝜈\nu 分别是 X𝑋XY𝑌Y 上的两个测度,使得 μ(X)=ν(Y)𝜇𝑋𝜈𝑌\mu(X)=\nu(Y)c(,)𝑐c(\cdot,\cdot) 是一个凸距离。约束条件 ν=Tμ𝜈𝑇𝜇\nu=T\sharp\mu ,“ T𝑇Tμ𝜇\mu 推到 ν𝜈\nu 上”对应于局部质量守恒约束。给定 X𝑋X 上的一个测度 μ𝜇\mu 和从 X𝑋XY𝑌Y 的映射 T𝑇TY𝑌Y 上的测度 Tμ𝑇𝜇T\sharp\mu ,称为“ μ𝜇\muT𝑇T 推送的前向”,满足所有 Borel 集合 BY𝐵𝑌B\subset Y 。因此,局部质量守恒约束意味着所有 Borel 集合 B𝐵B\subset Y𝑌Y

The local mass conservation constraint makes the problem very difficult: imagine now that you want to implement a computer program that enforces it: the constraint concerns all the subsets B𝐵B of Y𝑌Y. Could you imagine an algorithm that just tests whether a given map satisfies it ? What about enforcing it ? We will see below a series of transformations of the initial problem into equivalent problems, where the constraint becomes linear. We will finally end up with a simple convex optimization problem, that can be solved numerically using classical methods.
本地质量守恒约束使问题变得非常困难: 现在想象一下,您想要实现一个强制执行它的计算机程序: 约束涉及所有子集 B𝐵B Y𝑌Y 。 您能想象一个仅测试给定映射是否满足它的算法吗?关于强制执行它呢?我们将在下面看到一系列初始问题转化为等价问题的转换,约束变为线性。 最后,我们将得到一个简单的凸优化问题,可以使用经典方法进行数值解决。

Refer to caption


Figure 5: A classical example of the existence problem: there is no optimal transport between a segment L1subscript𝐿1L_{1} and two parallel segments L2subscript𝐿2L_{2} and L3subscript𝐿3L_{3} (it is always possible to find a better transport by replacing hh with h/22h/2).
图 5:存在问题的经典例子:在线段 L1subscript𝐿1L_{1} 和两个平行线段 L2subscript𝐿2L_{2}L3subscript𝐿3L_{3} 之间没有最佳传输(总是可以通过用 h/22h/2 替换 hh 找到更好的传输)。
Refer to caption
Figure 6: Four example of transport plans in 1D. A: a segment is translated. B: a segment is split into two segments. C: a Dirac mass is split into two Dirac masses; D: a Dirac mass is spread along two segments. The first two examples (A and B) have the form (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu where T𝑇T is a transport map. The third and fourth ones (C and D) have no corresponding transport map, because each of them splits a Dirac mass.
图 6:1D 运输方案示例。A:一个段被平移。B:一个段被分成两个段。C:一个 Dirac 质量被分成两个 Dirac 质量;D:一个 Dirac 质量沿两个段传播。前两个示例(A 和 B)的形式为 (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu ,其中 T𝑇T 是一个运输映射。第三个和第四个示例(C 和 D)没有对应的运输映射,因为它们每个都分割了一个 Dirac 质量。

Before then, let us get back to examine the original problem. The local mass conservation constraint is not the only difficulty: the functional optimized by Monge’s problem is non-symmetric, and this causes additional difficulties when studying the existence of solutions for problem (M). The problem is not symmetric because T𝑇T needs to be a map, therefore the source and target landscape do not play the same role. Thus, it is possible to merge earth (if T(x1)=T(x2)𝑇subscript𝑥1𝑇subscript𝑥2T(x_{1})=T(x_{2}) for two different points x1subscript𝑥1x_{1} and x2subscript𝑥2x_{2}), but it is not possible to split earth (for that, we would need a “map” T𝑇T that could send the same point x𝑥x to two different points y1subscript𝑦1y_{1} and y2subscript𝑦2y_{2}). The problem is illustrated in Figure 5: suppose that you want to compute the optimal transport between a segment L1subscript𝐿1L_{1} (that symbolizes a “wall of earth”) and two parallel segments L2subscript𝐿2L_{2} and L3subscript𝐿3L_{3} (that symbolize two “trenches” with a depth that correspond to half the height of the wall of earth). Now we want to transport the wall of earth to the trenches, to make the landscape flat. To do so, it is possible to decompose L1subscript𝐿1L_{1} into segments of length hh, sent alternatively towards L2subscript𝐿2L_{2} and L3subscript𝐿3L_{3} (Figure 5 on the left). For any length hh, it is always possible to find a better map T𝑇T, that is a lower value of the functional in (M), by subdividing L1subscript𝐿1L_{1} into smaller segments (Figure 5 on the right). The best way to proceed consists in sending from each point of L1subscript𝐿1L_{1} half the earth to L2subscript𝐿2L_{2} and half the earth to L3subscript𝐿3L_{3}, which cannot be represented by a map. Thus, the best solution of problem (M) is not a map. In a more general setting, this problem appears each time the source measure μ𝜇\mu has mass concentrated on a manifold of dimension d1𝑑1d-1 [McC95] (like the segment L1subscript𝐿1L_{1} in the present example).
在此之前,让我们回到检查原始问题。当地质量守恒约束并不是唯一的困难时:蒙热问题的优化功能是非对称的,这在研究问题(M)的解存在时导致额外困难。该问题不对称是因为 T𝑇T 需要是一张地图,因此源地形和目标地形扮演的角色并不相同。因此,可以合并大地(如果 T(x1)=T(x2)𝑇subscript𝑥1𝑇subscript𝑥2T(x_{1})=T(x_{2}) 两个不同点 x1subscript𝑥1x_{1}x2subscript𝑥2x_{2} ),但不可能分开地球(为此,我们需要一张“地图” T𝑇T 能将同一点 x𝑥x 发送到两个不同点 y1subscript𝑦1y_{1}y2subscript𝑦2y_{2} )。该问题在图 5 中得到了说明:假设你想要计算一个代表“一堵土墙”的线段 L1subscript𝐿1L_{1} 和两个平行线段 L2subscript𝐿2L_{2}L3subscript𝐿3L_{3} 之间的最佳传输(代表两个深度相当于土墙高度一半的“沟渠”)。现在我们想把土墙运输到沟渠,使地形平坦。为了做到这一点,可以将 L1subscript𝐿1L_{1} 分解为长度为 hh 的线段,交替地发送到 L2subscript𝐿2L_{2}L3subscript𝐿3L_{3} (左边的图 5)。 对于任意长度 hh ,总是可以通过将 L1subscript𝐿1L_{1} 细分为更小的段(右侧第 5 图)而找到一个更好的地图 T𝑇T ,即(M)中的功能值更低的地图。最佳操作方法是从 L1subscript𝐿1L_{1} 的每一点向 L2subscript𝐿2L_{2} 发送地球的一半,向 L3subscript𝐿3L_{3} 发送地球的一半,而这不能用地图表示。因此,问题(M)的最佳解决方案不是地图。在一个更一般的设定中,每当源测度 μ𝜇\mu 在一个维度 d1𝑑1d-1 的流形上有集中质量时[McC95](例如当前示例中的段 L1subscript𝐿1L_{1} )时,该问题会出现。

3 Kantorovich’s relaxed problem
3Kantorovich 的放松问题

To overcome this difficulty, Kantorovich stated a problem with a larger space of solutions, that is, a relaxation of problem (M), where mass can be both split and merged. The idea consists in solving for the “graph of T𝑇T” instead of T𝑇T. One may think of the graph of T𝑇T as a function g𝑔g defined on X×Y𝑋𝑌X\times Y that indicates for each couple of points xX,yYformulae-sequence𝑥𝑋𝑦𝑌x\in X,y\in Y how much matter goes from x𝑥x to y𝑦y. However, once again, we cannot use standard functions to represent the graph of T𝑇T: if you think about the graph of a univariate function xf(x)maps-to𝑥𝑓𝑥x\mapsto f(x), it is defined on 2superscript2\mathbb{R}^{2} but concentrated on a curve. For this reason, as in our previous example with factories, one needs to use measures. Thus, we are now looking for a measure γ𝛾\gamma supported by the product space X×Y𝑋𝑌X\times Y. The relaxed problem is stated as follows:
为了克服这一困难,坎托罗维奇提出了一个具有更大解空间的问题,即问题(M)的放松,其中质量既可以分裂也可以合并。这个想法在解决“ T𝑇T 的图”而不是 T𝑇T 时得以体现。我们可以将 T𝑇T 的图想象为定义在 X×Y𝑋𝑌X\times Y 上的函数 g𝑔g ,它指示每对点 xX,yYformulae-sequence𝑥𝑋𝑦𝑌x\in X,y\in Y 之间有多少物质从 x𝑥x 流向 y𝑦y 。然而,再一次,我们不能使用标准函数来表示 T𝑇T 的图:如果你想到一个一元函数 xf(x)maps-to𝑥𝑓𝑥x\mapsto f(x) 的图,它在 2superscript2\mathbb{R}^{2} 上定义,但集中在一条曲线上。因此,与我们之前关于工厂的例子一样,我们需要使用测度。因此,我们现在正在寻找一个支持产品空间 X×Y𝑋𝑌X\times Y 的测度 γ𝛾\gamma 。放松后的问题陈述如下:

infγ{X×Yc(x,y)𝑑γ|γ0 and γΠ(μ,ν)}where: Π(μ,ν)={γ𝒫(X×Y)|(PX)γ=μ;(PY)γ=ν}subscriptinfimum𝛾conditional-setsubscript𝑋𝑌𝑐𝑥𝑦differential-d𝛾𝛾0 and 𝛾Π𝜇𝜈where: Π𝜇𝜈conditional-set𝛾𝒫𝑋𝑌formulae-sequencesubscript𝑃𝑋𝛾𝜇subscript𝑃𝑌𝛾𝜈\begin{array}[]{l}\inf\limits_{\gamma}\left\{\int\limits_{X\times Y}c(x,y)d\gamma\ |\ \gamma\geq 0\mbox{ and }\gamma\in\Pi(\mu,\nu)\right\}\\[14.22636pt] \mbox{where: }\\[8.53581pt] \Pi(\mu,\nu)=\{\gamma\in{\cal P}(X\times Y)\ |\ (P_{X})\sharp\gamma=\mu\ ;\ (P_{Y})\sharp\gamma=\nu\}\end{array} (K)

where (PX)subscript𝑃𝑋(P_{X}) and (PY)subscript𝑃𝑌(P_{Y}) denote the two projections (x,y)X×Yx𝑥𝑦𝑋𝑌maps-to𝑥(x,y)\in X\times Y\mapsto x and (x,y)X×Yy𝑥𝑦𝑋𝑌maps-to𝑦(x,y)\in X\times Y\mapsto y respectively.
其中 (PX)subscript𝑃𝑋(P_{X})(PY)subscript𝑃𝑌(P_{Y}) 表示两个投影 (x,y)X×Yx𝑥𝑦𝑋𝑌maps-to𝑥(x,y)\in X\times Y\mapsto x(x,y)X×Yy𝑥𝑦𝑋𝑌maps-to𝑦(x,y)\in X\times Y\mapsto y

The two measures (PX)γsubscript𝑃𝑋𝛾(P_{X})\sharp\gamma and (PY)γsubscript𝑃𝑌𝛾(P_{Y})\sharp\gamma obtained by pushing forward γ𝛾\gamma by the two projections are called the marginals of γ𝛾\gamma. The measures γ𝛾\gamma in the admissible set Π(μ,ν)Π𝜇𝜈\Pi(\mu,\nu), that is, the measures that have μ𝜇\mu and ν𝜈\nu as marginals, are called optimal transport plans. Let us now have a closer look at the two constraints on the marginals (PX)γ=μsubscript𝑃𝑋𝛾𝜇(P_{X})\sharp\gamma=\mu and (PX)γsubscript𝑃𝑋𝛾(P_{X})\sharp\gamma that define the set of optimal transport plans Π(μ,ν)Π𝜇𝜈\Pi(\mu,\nu). Recalling the definition of the pushforward (previous subsection), these two constraints can also be written as:
通过两个投射获得的由 γ𝛾\gamma 推动而来的两个值 (PX)γsubscript𝑃𝑋𝛾(P_{X})\sharp\gamma(PY)γsubscript𝑃𝑌𝛾(P_{Y})\sharp\gamma 被称为 γ𝛾\gamma 的两个边际。在可接受集合 Π(μ,ν)Π𝜇𝜈\Pi(\mu,\nu)γ𝛾\gamma 度量,即具有 μ𝜇\muν𝜈\nu 作为边际的测度,被称为最优输运方案。现在让我们更仔细地看看定义最优输运方案 Π(μ,ν)Π𝜇𝜈\Pi(\mu,\nu) 集合的两个边际 (PX)γ=μsubscript𝑃𝑋𝛾𝜇(P_{X})\sharp\gamma=\mu(PX)γsubscript𝑃𝑋𝛾(P_{X})\sharp\gamma 的两个约束条件。回顾向前推进的定义(前面的小节),这两个约束条件也可以写成:

(PX)γ=μBX,B𝑑μ=B×Y𝑑γ(PY)γ=νBY,B𝑑ν=X×B𝑑γ.subscript𝑃𝑋𝛾𝜇iffformulae-sequencefor-all𝐵𝑋subscript𝐵differential-d𝜇subscript𝐵𝑌differential-d𝛾subscript𝑃𝑌𝛾𝜈iffformulae-sequencefor-allsuperscript𝐵𝑌subscriptsuperscript𝐵differential-d𝜈subscript𝑋superscript𝐵differential-d𝛾\begin{array}[]{lcl}(P_{X})\sharp\gamma=\mu&\iff&\forall B\subset X,\int_{B}d\mu=\int_{B\times Y}d\gamma\\[5.69054pt] (P_{Y})\sharp\gamma=\nu&\iff&\forall B^{\prime}\subset Y,\int_{B^{\prime}}d\nu=\int_{X\times B^{\prime}}d\gamma.\end{array} (1)

Intuitively, the first constraint (PX)γ=μsubscript𝑃𝑋𝛾𝜇(P_{X})\sharp\gamma=\mu means that everything that comes from a subset B𝐵B of X𝑋X should correspond to the amount of matter (initially) contained by B𝐵B in the source landscape, and the second one (PY)γ=νsubscript𝑃𝑌𝛾𝜈(P_{Y})\sharp\gamma=\nu means that everything that goes into a subset Bsuperscript𝐵B^{\prime} of Y𝑌Y should correspond to the (prescribed) amount of matter contained by Bsuperscript𝐵B^{\prime} in the target landscape ν𝜈\nu.
直观上,第一个约束条件 (PX)γ=μsubscript𝑃𝑋𝛾𝜇(P_{X})\sharp\gamma=\mu 意味着来自 X𝑋X 的子集的一切应该对应于来源景观 B𝐵B 中包含的物质量(最初),而第二个条件 (PY)γ=νsubscript𝑃𝑌𝛾𝜈(P_{Y})\sharp\gamma=\nu 意味着进入 Y𝑌Y 的子集的一切应该对应于目标景观 ν𝜈\nuBsuperscript𝐵B^{\prime} 所包含的(规定的)物质量。

Refer to caption

Figure 7: A discrete version of Kantorovich’s problem.
图 7:康托罗维奇问题的离散版本。

We now examine the relation between the relaxed problem (K) and the initial problem (M). One can easily check that among the optimal transport plans, those with the form (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu correspond to a transport map T𝑇T:
我们现在研究松弛问题(K)与初始问题(M)之间的关系。可以很容易地检查到,在最优输运方案中,那些形式为 (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu 的方案 对应于一个输运映射 T𝑇T

Observation 1.

If (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu is a transport plan, then T𝑇T pushes μ𝜇\mu onto ν𝜈\nu.


观察 1. 如果 (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu 是一个输运方案,则 T𝑇T 会将 μ𝜇\mu 推送到 ν𝜈\nu
Proof.

(Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu is in Π(μ,ν)Π𝜇𝜈\Pi(\mu,\nu), thus (PY)(Id×T)μ=νsubscript𝑃𝑌𝐼𝑑𝑇𝜇𝜈(P_{Y})\sharp(Id\times T)\sharp\mu=\nu, or ((PY)(Id×T))μ=νsubscript𝑃𝑌𝐼𝑑𝑇𝜇𝜈\left((P_{Y})\circ(Id\times T)\right)\sharp\mu=\nu, and finally Tμ=ν𝑇𝜇𝜈T\sharp\mu=\nu. ∎


证明。 (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\muΠ(μ,ν)Π𝜇𝜈\Pi(\mu,\nu) 中,因此 (PY)(Id×T)μ=νsubscript𝑃𝑌𝐼𝑑𝑇𝜇𝜈(P_{Y})\sharp(Id\times T)\sharp\mu=\nu ,或 ((PY)(Id×T))μ=νsubscript𝑃𝑌𝐼𝑑𝑇𝜇𝜈\left((P_{Y})\circ(Id\times T)\right)\sharp\mu=\nu ,最终 Tμ=ν𝑇𝜇𝜈T\sharp\mu=\nu 。∎

We can now observe that if a transport plan γ𝛾\gamma has the form γ=(Id×T)μ𝛾𝐼𝑑𝑇𝜇\gamma=(Id\times T)\sharp\mu, then problem (K) becomes:
我们现在可以观察到,如果一个运输计划 γ𝛾\gamma 的形式为 γ=(Id×T)μ𝛾𝐼𝑑𝑇𝜇\gamma=(Id\times T)\sharp\mu ,那么问题(K)就变成了:

min{X×Yc(x,y)d((Id×T)μ)}=min{Xc(x,T(x))dμ)\mbox{min}\left\{\int\limits_{X\times Y}c(x,y)d\left((Id\times T)\sharp\mu\right)\right\}\quad=\quad\mbox{min}\left\{\int\limits_{X}c(x,T(x))d\mu\right)

(one retrieves the initial Monge problem).
(其中一个是检索最初的蒙日问题)。

To further help grasping an intuition of this notion of transport plan, we show four 1D examples in Figure 6 (the transport plan is then 1D×1D=2D1𝐷1𝐷2𝐷1D\times 1D=2D). Intuitively, the transport plan γ𝛾\gamma may be thought of as a “table” indexed by x𝑥x and y𝑦y that indicates the quantity of matter transported from x𝑥x to y𝑦y. More exactly333We recall that one cannot evaluate a measure γ𝛾\gamma at a point (x,y)𝑥𝑦(x,y), we can just compute integrals with γ𝛾\gamma.
我们回顾一下,不能在点 (x,y)𝑥𝑦(x,y) 处评估度量 γ𝛾\gamma ,我们只能计算 γ𝛾\gamma 的积分。

为了进一步帮助理解这种运输计划的概念,我们在图 6 中展示了四个 1D 示例(然后运输计划为 1D×1D=2D1𝐷1𝐷2𝐷1D\times 1D=2D )。直觉上,运输计划 γ𝛾\gamma 可以被认为是由 x𝑥xy𝑦y 索引的“表”,指示从 x𝑥x 运输到 y𝑦y 的物质数量。 更确切地说 3
, the measure γ𝛾\gamma is non-zero on subsets of X×Y𝑋𝑌X\times Y that contain points (x,y)𝑥𝑦(x,y) such that some matter is transported from x𝑥x to y𝑦y. Whenever γ𝛾\gamma derives from a transport map T𝑇T, that is if γ𝛾\gamma has the form (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu, then we can consider γ𝛾\gamma as the “graph of T𝑇T” like in the first two examples of Figure 6 (A) and (B)444Note that the measure μ𝜇\mu is supposed to be absolutely continuous with respect to the Lebesgue measure. This is required, because for instance in example (B) of Figure 6, the transport map T𝑇T is undefined at the center of the segment. The absolute continuity requirement allows one to remove from X𝑋X any subset with zero measure.
注意,度量 μ𝜇\mu 应该对勒贝格测度是绝对连续的。 这是必需的,因为例如在图 6 的示例(B)中,运输映射 T𝑇T 在该段的中心处是未定义的。 绝对连续性要求允许从 X𝑋X 中去除任何零度量子集。

,度量 γ𝛾\gamma 在包含点 (x,y)𝑥𝑦(x,y)X×Y𝑋𝑌X\times Y 的子集上非零,点 (x,y)𝑥𝑦(x,y) 使从 x𝑥xy𝑦y 转移了一些物质。每当 γ𝛾\gamma 由运输图 T𝑇T 推导出来时,即如果 γ𝛾\gamma 具有形式 (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu ,那么我们可以将 γ𝛾\gamma 视为“ T𝑇T 的图”,就像图 6(A)和(B)的前两个示例中 4
in Figure 6. 在图 6 中。

The transport plans of the two other examples (C) and (D) have no associated transport map, because they split Dirac masses. The transport plan associated with Figure 5 has the same nature (but this time in 2D×2D=4D2𝐷2𝐷4𝐷2D\times 2D=4D). It cannot be written with the form (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu because it splits the mass concentrated in L1subscript𝐿1L_{1} into L2subscript𝐿2L_{2} and L3subscript𝐿3L_{3}.
另外两个示例(C)和(D)的运输计划没有关联的传输地图,因为它们分裂了狄拉克质量。与图 5 相关的运输计划具有相同的性质(但这次是在 2D×2D=4D2𝐷2𝐷4𝐷2D\times 2D=4D )。它不能用形式 (Id×T)μ𝐼𝑑𝑇𝜇(Id\times T)\sharp\mu 来写,因为它将集中在 L1subscript𝐿1L_{1} 的质量分裂成 L2subscript𝐿2L_{2}L3subscript𝐿3L_{3}

Now the theoretical questions are:
现在的理论问题是:

  • when does an optimal transport plan exist ?


    • 何时存在最优输运方案?
  • when does it admit an associated optimal transport map ?


    • 何时承认其存在关联的最优输运图?

A standard approach to tackle this type of existence problem is to find a certain regularity both in the functional and in the space of the admissible transport plans, that is, proving that the functional is sufficiently “smooth” and finding a compact set of admissible transport plans. Since the set of admissible transport plans contains at least the product measure μνtensor-product𝜇𝜈\mu\otimes\nu, it is non-empty, and existence can be proven thanks to a topological argument that exploits the regularity of the functional and the compactness of the set. Once the existence of a transport plan is established, the other question concerns the existence of an associated transport map. Unfortunately, problem (K) does not directly show the structure required by this reasoning path. However, one can observe that (K) is a linear optimization problem subject to linear constraints. This suggests using certain tools, such as the dual formulation, that was also developed by Kantorovich. With this dual formulation, it is possible to exhibit an interesting structure of the problem, that can be used to answer both questions (existence of a transport plan, and existence of an associated transport map).
一种解决这种类型存在问题的标准方法是在可传递计划的函数和空间中找到一定的规律,即证明函数足够"平滑"并找到一组可接受的紧致传输计划集。由于可接受传输计划集至少包含乘积度量 μνtensor-product𝜇𝜈\mu\otimes\nu ,因此它不为空,并且可以通过利用函数的规则性和集合的紧致性所做的拓扑论证来证明它的存在性。一旦传输计划的存在性确立,另一个问题涉及相关传输映射的存在性。不幸的是,问题(K)并未直接显示出这种推理路径所需的结构。然而,我们可以观察到(K)是一个受线性约束的线性优化问题。这表明可以使用某些工具,例如康托洛维奇也开发的对偶形式。通过这种对偶形式,可以展示出该问题的一个有趣结构,可用来回答两个问题(传输计划的存在性和相关传输映射的存在性)。

4 Kantorovich’s dual problem
4Kantorovich 的对偶问题

Kantorovich’s duality applies to problem (K), in its most general form (with measures). To facilitate understanding, we will consider instead a discrete version of problem (K), where the involved entities are vectors and matrices (instead of measures and operators). This makes it easy to better discern the structure of (K), that is the linear nature of both the functional and the constraints. This also makes it easier for the reader to understand how to construct the dual by manipulating simpler objects (matrices and vectors), however the structure of the reasoning is the same in the general case.
Kantorovich 的对偶性适用于问题 (K),以其最一般形式 (带有度量)。为了方便理解,我们将考虑问题 (K) 的离散版本,其中涉及的实体是向量和矩阵 (而不是度量和算子)。这样能更容易地辨别问题 (K) 的结构,即泛函和约束的线性性质。这也使读者更容易理解如何通过操作更简单的对象 (矩阵和向量) 构造对偶问题,然而,在一般情况下,推理的结构是相同的。

4.1 The discrete Kantorovich problem
4.1 离散 Kantorovich 问题

In Figure 7, we show a discrete version of the 1D transport between two segments of Figure 6. The measures μ𝜇\mu and ν𝜈\nu are replaced with vectors U=(ui)i=1m𝑈subscriptsubscript𝑢𝑖𝑖1𝑚U=(u_{i})_{i=1\ldots m} and V=(vj)i=1n𝑉subscriptsubscript𝑣𝑗𝑖1𝑛V=(v_{j})_{i=1\ldots n}. The transport plan γ𝛾\gamma becomes a set of coefficients γijsubscript𝛾𝑖𝑗\gamma_{ij}. Each coefficient γijsubscript𝛾𝑖𝑗\gamma_{ij} indicates the quantity of matter that will be transported from uisubscript𝑢𝑖u_{i} to vjsubscript𝑣𝑗v_{j}. The discrete Kantorovich problem can be written as follows:
在图 7 中,我们展示了图 6 中两个区段之间的一维传输的离散版本。测度 μ𝜇\muν𝜈\nu 被向量 U=(ui)i=1m𝑈subscriptsubscript𝑢𝑖𝑖1𝑚U=(u_{i})_{i=1\ldots m}V=(vj)i=1n𝑉subscriptsubscript𝑣𝑗𝑖1𝑛V=(v_{j})_{i=1\ldots n} 替换。传输计划 γ𝛾\gamma 成为一组系数 γijsubscript𝛾