Accelerating operator Sinkhorn iteration with overrelaxation

技术摘要：利用超松弛加速算子 Sinkhorn 迭代

问题陈述
本文解决了算子缩放问题，该问题旨在寻找可逆方阵 $L \in GL_m(\mathbb{R})$ 和 $R \in GL_n(\mathbb{R})$，将给定的矩阵集合 $A_1, \dots, A_k \in \mathbb{R}^{m \times n}$ 联合变换为“缩放”形式 $\bar{A}_i = L A_i R^\top$。目标是同时满足以下两个条件：

1. $\sum_{i=1}^k \bar{A}_i \bar{A}_i^\top = \frac{1}{m} I_m$
2. $\sum_{i=1}^k \bar{A}_i^\top \bar{A}_i = \frac{1}{n} I_n$

该问题推广了经典的矩阵缩放，并出现在非交换多项式恒等式测试、不变量理论和信号处理等应用中。标准的求解方法是算子 Sinkhorn 迭代（OSI），这是一种交替不动点算法。虽然 OSI 在特定条件下具有全局收敛性，但其收敛速度可能较慢。作者旨在利用**逐次超松弛（SOR）**技术加速这一过程，该技术在线性系统中已确立，但在这一特定的非线性算子缩放背景下探索较少。

方法论
作者提出了三种不同的算子 Sinkhorn 迭代超松弛变体，均基于将问题解释为正定（PD）矩阵锥上的交替最小化。

1. 欧几里得超松弛（PD-OR）： 该方法对迭代序列 $(X_t, Y_t)$ 应用标准的仿射组合，其中 $X_t = L_t^\top L_t$ 且 $Y_t = R_t^\top R_t$。更新规则为 $(1-\omega)X_t + \omega S_1(Y_t)$，其中 $S_1$ 是缩放映射。虽然计算简单，但当松弛参数 $\omega > 1$ 时，该方法缺乏理论保证，无法确保生成的矩阵保持正定性。
2. 坐标变换超松弛（Cholesky-OR）： 为了确保迭代序列保持在 PD 锥内，作者建议在变换后的坐标空间中应用超松弛。他们具体利用了 PD 矩阵的Cholesky 因子（$L$ 和 $R$）。由于 Cholesky 因子属于线性空间（三角矩阵），仿射组合是明确定义的，并保留了算法所需的结构。该变体被展示为数值效率最高。
3. 测地线超松弛（Geodesic-OR）： 该方法尊重由Hilbert 度量诱导的 PD 锥的双曲几何结构。作者不使用仿射组合，而是定义沿测地线的更新，使用算子几何平均 $X \#_\omega \tilde{X}$。这种方法在理论上具有鲁棒性，保持了问题的轨道等变性，并确保迭代序列保持在 PD 锥内。

主要贡献与理论结果

• 局部收敛性分析： 作者证明，在不动点附近，所有三种超松弛变体在一阶上是等价的。通过线性化迭代并利用轨道等变性（对解轨道缩放的不变性），他们推导出了渐近局部收敛速率的统一公式。

  • 他们确立了线性化 SOR 迭代的谱半径遵循经典的Young SOR 定理模式。
  • 他们提供了一个渐近最优松弛参数 $\omega_{opt}$ 的公式，该公式取决于标准（未松弛）算子 Sinkhorn 迭代的谱半径 $\beta$：$\omega_{opt} = \frac{2}{1 + \sqrt{1-\beta^2}}$。
  • 该分析基于这样一个事实：底层测地线凸目标函数的 Hessian 矩阵具有一个对应于缩放轨道的一维零空间，这一性质他们已严格证明。

• 测地线 SOR 的全局收敛性： 虽然非线性 SOR 的全局收敛性通常难以证明，但作者证明了Geodesic-OR变体在特定 $\omega$ 范围内具有全局收敛性。

  • 他们利用了Hilbert 度量以及标准 Sinkhorn 迭代的收缩性。
  • 一项新颖的贡献是 PD 矩阵上 Hilbert 度量的度量不等式（引理 3.4），该不等式界定了测地线点与第三点之间的距离。该不等式使他们能够将收缩性结果扩展到超松弛情况，证明了当 $\omega \in (0, \frac{2}{1+\sqrt{\Lambda_1 \Lambda_2}})$ 时的收敛性，其中 $\Lambda_1, \Lambda_2$ 是缩放映射的 Lipschitz 常数。

• 自适应参数选择： 认识到最优 $\omega$ 取决于特定实例未知的收敛速率，作者采用了一种自适应策略。他们从标准方法的初始迭代中估计收敛速率 $\beta$，并将 $\omega$ 动态更新为 $\omega_{opt}$，这一技术借鉴了近期关于矩阵缩放的研究成果。

数值结果
作者在两类实例上进行了实验：

1. 框架缩放： 在此应用中，SOR 方法（特别是 Cholesky-OR 和 Geodesic-OR）表现出比标准 OSI 显著更快的收敛速度。这些方法在大约达到 OSI 所需迭代次数的一半时，就实现了 $10^{-14}$ 量级的误差。观察到的收敛速率与理论预测非常吻合。
2. 病态算子： 使用希尔伯特矩阵作为输入，作者观察到，虽然 SOR 在初始阶段加速了收敛，但其最终精度（$10^{-6}$）低于标准 OSI（$10^{-11}$）。他们将此归因于基于“半缩放”中间矩阵的 SOR 变体未能像标准 OSI 中的完整交替更新那样有效地补偿初始的病态条件。

意义与主张
本文声称将现有的矩阵缩放结果（特别是 Thibault 等人及 Lehmann 等人的工作）推广到更复杂的算子缩放场景。

• 理论洞察： 作者强调，他们严谨的局部收敛性分析处理了由于群等变性导致的 Hessian 矩阵非正定性质，为算子缩放问题的结构提供了新的见解。
• 实用价值： 数值实验表明，在条件良好的场景（如框架缩放）中，超松弛可以将算子缩放加速数个数量级，且计算开销可忽略不计，特别是当使用基于 Cholesky 的方法时。
• 局限性： 作者谦逊地承认，他们对测地线版本的全局收敛性证明所覆盖的 $\omega$ 范围可能过于悲观（通常接近 1），并且当前的 SOR 实现在病态输入上可能会遭受数值精度降低的问题。他们指出，为更广泛的 $\omega$ 范围建立全局收敛性并提高病态问题的精度是未来的工作方向。