“Sinkhorn 矩阵缩放提供一个具有明确约束含义的交替迭代:先修正行边缘,再修正列边缘,严格正核下收敛到唯一缩放计划。每次只保证刚修正的一侧精确满足,因此停止时应检查两侧残差,而不只观察系…”
形式陈述
已知熵正则最优计划形如
设
其中
直觉
固定列缩放
每次更新保持正性以及“对同一个
为什么交替缩放确实收敛
把初始矩阵
修列时同理。于是
固定边缘时,
由有限维的Bolzano–Weierstrass 定理,可从迭代矩阵抽取收敛子列。共同正下界使散度在这些矩阵上连续;若相邻两步的差没有趋零,再抽取一对极限就会得到散度为零而两表不同,矛盾。每步精确满足一侧边缘,因此任意子列极限
例子与边界
取
第一轮
列和已是
实作时应计算
而非只观察系数变化。边缘残差控制可行性;若还需严格的目标误差证书,应构造可行计划及相应对偶界。只做固定轮数而不报告残差,无法判断结果是否达到要求。
稠密矩阵每轮两次矩阵向量乘法,时间
对数域避免下溢
当
列更新同理;
推论与应用
Sinkhorn 求解的是给定
参考资料
- Gabriel Peyré and Marco Cuturi, 2019,§4.2、§4.4, Sinkhorn and log-domain computations。
- Marco Cuturi, 2013,§4.1, Computing Sinkhorn distances。