Computational Optimal Transport笔记——第二章(2)
符号说明
耦合矩阵 coupling matrix: ,其中代表从 bin 移动到 bin (或者在离散情况下从移动到)的质量。
Admissible coupling:
(行和为向量,列和为向量的矩阵)
:在离散测度下的 Kantorovich problem。
在任意测度下的 Kantorovich problem
p-Wasserstein distance:
在任意测度中的 p-Wasserstein distance:
2. 理论基础
2.3 Kantorovich Relaxation
Kantorovich
Kantorovich 的核心思想是放松交通的确定性,即一个源点只能被分配到另一个点或位置或者。Kantorovich 建议 在任何地点的质量有可能被分配到几个地点。即Kantorovich 不再认为质量运输应该是确定性的,而是考虑一种概率运输,这种概率运输允许质量从一个源头分裂到几个目标。
不是使用排列或者 map ,而是使用 coupling matix,其中代表从 bin 移动到 bin (或者在离散情况下从移动到)的质量。
Admissible coupling的特征有:
【行和为向量,列和为向量】
可以看出,矩阵集合被个等式约束,是一个凸多面体。
Kantorovich 的对称性
Kantorovich’s relaxed formulation是对称的,即耦合矩阵在中当且仅当在中。
Kantorovich’s optimal transport problem
Kantorovich’s optimal transport problem是
这是一个线性规划问题,与此类程序的通常情况一样,它的最佳解决方案不一定是惟一的。
Remark 2.10 (矿山和工厂)略
Permutation matrices as couplings 对于排列,我们将对应的排列矩阵写为
此时有
这表明assigment problem可以写为Kantorovich problem,当的约束为排列矩阵:
可以计算得,,但是不是在 中所有的矩阵都是排列矩阵,例如。因此更小
接下来的定理说明两个问题有相同的最小值,也就是说可以找到一个permutation matrix最小化当 下 Kantorovich problem。
Remark 2.11(在离散测度下的 Kantorovich problem)对于离散测度,将于的支撑集中的点两两之间的cost记入矩阵,,定义
是支撑集中的概率权重向量。
Remark 2.12(使用 optimal assigments and couplings)OT问题的应用。
可作为阅读文献
Remark 2.13(任意测度下的 Kantorovich problem)在乘积空间上的联合分布中考虑 couplings
在离散测度下
在一般情况下,mass conservation constraint可以被写为联合概率分布下的 marginal constraint
定义投影
KaTeX parse error: Expected '}', got '#' at position 14: P_{\mathcal{X#̲}}和KaTeX parse error: Expected '}', got '#' at position 14: P_{\mathcal{Y#̲}} 是投影的 push-forward。
这些 marginal constraints等价于
Kantorovich问题(2.11)可以一般化为
这是一个在测度空间上的无限维的线性规划问题。如果是紧空间,是连续函数,这个问题总是有解。
Remark 2.14(概率解释)Kantorovich’s problem可以通过随机变量解释,问题(2.15)可以等价为
其中是在上的随机变量,并且,
2.4 Optimal Transport 的度量性质
实际上,OT可以被理解为一种将点与点之间的地面距离提升到直方图或度量值之间距离的标准方法。我们考虑这种情况 “ground metric” matrix 是固定的,代表 bins 之间的可替换 cost,并且在我们希望比较的 histogram 间共享。接下来的 Proposition 说明 OT 提供了在 bins 支撑下的 histogram 之间的合理距离。
Proposition 2.2 我们假设 ,对于一些 ,,其中 是 上的距离,即
令
定义了在上的 p-Wasserstein distance。可证明是对称、正定、满足三角不等式
Remark 2.15(在的情况)注意到如果,是 itself distance。
根据 Proposition 2.2 和 Remark 2.15,当 时,是单纯形之间的距离。当时,是纯形之间的距离。
Remark 2.16(Wasserstein distance 的应用)
Remark 2.17(在测度间的 Wasserstein distance)Proposition 2.2 可以被一般化为处理任意测度。
Proposition 2.3 假设,其中 是 上的距离,即
则在 上的 p- Wasserstrin distance 可以表示为
可证明具有对称、非负和三角不等式
Remark 2.18(几何直觉和弱收敛)Wasserstein距离最重要的一个性质就是它是一个弱距离,即它允许比较支撑集不重叠的奇异分布(例如,离散分布)并量化两个分布之间的空间位移。
在经典的距离(或收敛)不会在离散分布中定义(L2范数只能应用于相对于基础测度具有密度的连续测度,而离散L2范数要求位置(xi, yj)取预先确定的离散集中的值才能正常工作)。
鲜明对比的是,对于任何,。
注意到 ,因此Kantorovich问题有唯一可行解,,
。这说明如果 , 。这说明是一种弱收敛的方式。
定义 2.2(弱收敛)为紧区域,在中 弱收敛于当且仅当对于任何连续函数,
记为。
如果对于非紧区域,需要对加上另外的条件。这个弱收敛的概念对应于随机向量法则中的收敛。
可以证明弱收敛和是等价的。(对于*度量空间,将矩收敛到p阶。)
Remark 2.19(平移)在欧几里得空间 ,ground cost 的 Wasserstein distance的特征是解析为平移,即为平移算子,有
其中是的均值。特别,这个距离可以分解为
其中是“居中的”零平均度量
Remark 2.20(当的情况)当时为
相比于的情况,这是一个非凸优化问题,难于数值求解和理论研究。距离与在支撑下的Hausdorff距离有关。