首次给出Sinkhorn-Knopp算法的非渐近局部收敛分析，精度提升显著。
Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
- 基于连通性条件建立非渐近局部收敛理论，匹配已有渐近分析速率。
- 证明在稠密矩阵下，算法复杂度从O(n^{7/3}/ε^{2/3})优化至O(n^{9/4}/√ε)。
- 揭示原SK算法局部次优性，并提出加速变体，适合高精度矩阵缩放场景。
我们重新研究用于矩阵缩放问题的Sinkhorn-Knopp（SK）算法。尽管关于SK及其变体的全局收敛性已有大量文献，但其局部线性收敛行为仍不清晰。本文首次提供了与现有渐近雅可比分析所得速率一致的非渐近局部分析。在特定连通性条件下，证明了SK是双重随机矩阵缩放的多项式时间算法。利用所发展的工具，展示了SK的局部次优性，并提出了加速版本。对于稠密矩阵，将现有的一阶矩阵缩放算法复杂度从O(n^{7/3}/ε^{2/3})改进为O(n^{9/4}/√ε)。
原文摘要 · Abstract (English)
We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We show that under certain connectivity conditions, SK is a polynomial-time algorithm for doubly stochastic matrix scaling. With the developed tools, we showcase the local suboptimality of SK and provide accelerated variants. Finally, for dense matrices, we improve the complexity of existing first-order matrix scaling algorithms from $O(\tfrac{n^{7/3}}{\varepsilon^{2/3}})$ to $O(\tfrac{n^{9/4}}{\sqrt{\varepsilon}})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。