最优传输问题假设有MMM堆土，每堆土的大小是ama_mam​，有NNN个坑，每个坑的大小是bnb_nbn​，把单位土从土堆mmm运送到坑nnn的代价是c(m,n)c(m,n)c(m,n)，如何找到一种运输方法填满坑，并且代价最小，这就是最优传输问题（optimaltransport(OT)problem）。假设有两个概率分布，如何以最小的成本将一种概率分布转换为另一种概率分布，这也是最优传输问题。这个最小的成本可以作为度量两个概率分布的距离，被称为Wasserstein距离，或者推土机距离（EarthMover’sDistance（EMD））。在离散的情况下，假设r,c∈R+d\mathbfr

Sinkhorn-Knopp是为了解决最优传输问题所提出的。Sinkhorn算法原理最优运输问题的目标就是以最小的成本将一个概率分布转换为另一个概率分布。即将概率分布c以最小的成本转换到概率分布r，此时就要获得一个分配方案P∈Rn×m其中需满足以下条件：P的行和服从分布rP的列和服从分布c因此在分布r、c约束下，P的解空间可以做如下定义：同时希望最小化转换成本，即需要一个成本矩阵（costmatrix）M。于是就有了最优传输问题的公式化表示：此时为Wassersteinmetric或earthmoverdistance（EMD推土机距离）代价函数。Sinkhorn距离是对推土机距离的一种改进，

目录1引言2例子：分甜点3最优传输问题4Sinkhorn算法4.1Sinkhorn距离4.2算法流程4.3代码实验1引言最近看到一篇特征匹配相关的论文，思想是将特征匹配问题转化为最优传输问题求解，于是我去学习了一下最优传输问题。本文主要是对博文NotesonOptimalTransport的学习做一个记录总结，该博文写的不错，推荐阅读。2例子：分甜点文章作者以一个简单的甜点分配例子引入了最优传输问题。向量r=[3,3,3,4,2,2,2,1]⊤\mathbf{r}=[3,3,3,4,2,2,2,1]^{\top}r=[3,3,3,4,2,2,2,1]⊤表示n=8n=8n=8个人需要的甜点数：向