1. 什么是最优传输

2. 基本概念

3.1 离散测度 (Discrete measures)

首先，说一下概率向量（或者称为直方图，英文：Histograms， probability vector）的定义：

上述公式的含义：一个长度为n的数组，每个元素的值在[0, 1]之间，并且该数组的和为1，即表示的是一个概率分布向量。

比如[0.1，0.2，0.3，0.4]就是一个概率向量。

离散测度：所谓测度就是一个函数，把一个集合中的一些子集（符合上述概率分布向量）对应给一个数[4]。具体公式定义如下：

上述公式含义：以 $a_{i}$ 为概率和对应位置 $x_{i}$ 的狄拉克δ函数值乘积的累加和。下图很好地阐述了一组不同元素点的概率向量分布：

上图中红色点是均匀的概率分布，蓝色点是任意的概率分布。点状分布对应是一维数据的概率向量分布，而点云状分布对应的是二维数据的概率向量分布。

3.2 蒙日(Monge)问题

蒙日(Monge)问题的定义：找出从一个 measure(测度)到另一个measure的映射，使得所有 $c (x_{i}, y_{j})$ 的和最小，其中 $c$ 表示映射路线的运输代价，需要根据具体应用定义。蒙日问题具体的定义公式如下：

对于上述公式的解释可以采用离散测度来解释，对于两个离散测度：

找到一个n维映射到m维的一个映射，使得

上述映射的示意图如下：

对于上述的映射公式，结合蒙日问题的定义公式，可以归纳如下：

上述公式的含义：通过这个映射 $T (x_{i})$ 的转移，使得转移到 $b_{j}$ 的所有 $a_{i}$ 的值的和刚好等于 $b_{j}$ （其中要求，所有 $a_{i}$ 必须转走，而所有 $b_{j}$ 必须收到预期的货物），即我需要多少就给运输转移多少，不能多也不能少。其中 $c ()$ 表示运输代价， $T (x_{i})$ 表示映射的运输方案。

3.3 Kantorovich Relaxation (松弛的蒙日问题)

蒙日问题是最优运输的起初最重要的思想，然而其有一个很大的缺点: 从a的所有货物运输到b时，只能采用原始的货物大小进行运算，即不能对原始的货物进行拆开发送到不同目的地。而Kantorovich Relaxation则对蒙日问题进行了松弛处理，即原始的货物可以分开发送到不同目的地，也可以把蒙日问题理解为Kantorovich Relaxation的一个映射运输特例。具体区别可以参考下图[2]。

符合Kantorovich Relaxation的映射运输定义公式如下：

区别于蒙日问题要求映射运输的所有 $a_{i}$ 一对一转走到 $b_{j}$ 。Kantorovich Relaxation只要求，所有每个 $a_{i}$ 中获取能够完全转走，可以是只转给一个 $b_{j}$ ，也可以是多个 $b_{j}$ ，但是要确保每个 $b_{j}$ 只需要收取预期要求的货物即可。简单地描述：行求和对应向量a, 列向量求和对应向量 b.具体的传输示例如下：