Sinkhorn 矩阵缩放算法

固定列缩放 $v$ 时，当前第 $i$ 行总量是 $u_i(Kv{)}_i$，所以把 $u_i$ 调成 $a_i/(Kv{)}_i$，就精确修好所有行。同理，固定 $u$ 后修列。第二次修正一般会再次改变行和，因此必须继续交替。

每次更新保持正性以及“对同一个 $K$ 只作行列缩放”的结构。刚修正的一侧边缘精确满足，另一侧逐渐接近。收敛可以直接由相对熵恒等式证明，而不把它当作普通欧氏投影。

为什么交替缩放确实收敛 ​

把初始矩阵 $K\mathrm{diag}(v^{(0)})$ 除以其元素总和，记所得严格正概率表为 $R$。逐次修行、修列得到概率表 $Q^0=R,Q^1,Q^2,\dots$；每两步对应算法的一整轮。初始归一化只改变无关的缩放常数。对任意满足两组边缘的 $P$，以自然对数记 $D(P\Vert Q)=\sum P_{ij}\log \left(P_{ij}/Q_{ij}\right)$。一次修行使 $\log \left(Q_{ij}^{r+1}/Q_{ij}^r\right)$ 只依赖行号，而 $P$ 与 $Q^{r+1}$ 行和相同，故

修列时同理。于是

固定边缘时，$D(P\Vert R)$ 与本页熵正则目标只差一个正常数倍及加法常数，所以其最小者是已知严格正的唯一计划 $P^{\ast }$。在 (1) 中取 $P=P^{\ast }$，得 $D(P^{\ast }\Vert Q^N)$ 一致有界。由于每个 $P_{ij}^{\ast }>0$，而所有概率表项不超过 $1$，这迫使全部 $Q_{ij}^N$ 有共同正下界；否则某项 $-P_{ij}^{\ast }\log Q_{ij}^N$ 会发散。各步散度非负，其和有界，所以 $D(Q^{r+1}\Vert Q^r)\to 0$。

由有限维的Bolzano–Weierstrass 定理公理库Bolzano–Weierstrass 定理Bolzano–Weierstrass theorem实数空间中的每个有界序列都存在收敛子列。，可从迭代矩阵抽取收敛子列。共同正下界使散度在这些矩阵上连续；若相邻两步的差没有趋零，再抽取一对极限就会得到散度为零而两表不同，矛盾。每步精确满足一侧边缘，因此任意子列极限 $Q$ 同时满足两侧边缘。设 (1) 中的部分和趋于 $S$，沿 $Q^{N_j}\to Q$ 分别取 $P=Q$ 与 $P=P^{\ast }$，得到

$P^{\ast }$ 的最优性给第二个左侧不大于第一个左侧，故 $D(P^{\ast }\Vert Q)=0$，即 $Q=P^{\ast }$。所有子列极限相同，整个计划序列便收敛。这个论证给出收敛性，没有给出与矩阵条件无关的统一迭代轮数。

取

第一轮 $u^{(1)}=(1/3,1/3)$，随后 $v^{(1)}=(1/2,3/2)$，故

列和已是 $1/4,3/4$，行和却是 $5/12,7/12$。这明确展示“修好列”没有同时保证行。第二轮行缩放为 $u^{(2)}=(2/5,2/7)$，再修列后，行边缘的 $L^1$ 残差从 $1/6$ 降为 $9/646$，列残差仍为零。

实作时应计算

而非只观察系数变化。边缘残差控制可行性；若还需严格的目标误差证书，应构造可行计划及相应对偶界。只做固定轮数而不报告残差，无法判断结果是否达到要求。

稠密矩阵每轮两次矩阵向量乘法，时间 $O(mn)$；$K$ 的存储为 $O(mn)$，两组缩放向量为 $O(m+n)$。迭代轮数还取决于矩阵条件、正则参数与容许误差，不能把总成本也无条件写成 $O(mn)$。

对数域避免下溢 ​

当 $C_{ij}/\epsilon$ 很大，直接计算 $K_{ij}$ 可能变成机器零。令 $f=\epsilon \log u$、$g=\epsilon \log v$，行更新改写为

列更新同理；$\mathrm{LSE}(z)=\log \sum _j{e}^{z_j}$ 通过先减最大值稳定计算。零边缘应先删除，真正的零核元素则需要支持可行性条件，不能用除零继续迭代。

Sinkhorn 求解的是给定 $\epsilon$ 的正则问题。即使边缘残差已经很小，仍有熵正则化相对于原输运问题的偏差。对计算报告而言，至少应一起给出 $\epsilon$、边缘残差和所报告成本的定义，才能让结果可复核。