{"ID":2895270,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.09711","arxiv_id":"2507.09711","title":"Phase transition of the Sinkhorn-Knopp algorithm","abstract":"The matrix scaling problem, particularly the Sinkhorn-Knopp algorithm, has been studied for over 60 years. In practice, the algorithm often yields high-quality approximations within just a few iterations. Theoretically, however, the best-known upper bound places it in the class of pseudopolynomial-time approximation algorithms. Meanwhile, the lower-bound landscape remains largely unexplored. Two fundamental questions persist: what accounts for the algorithm's strong empirical performance, and can a tight bound on its iteration count be established? For an $n\\times n$ matrix, its normalized version is obtained by dividing each entry by its largest entry. We say that a normalized matrix has a density $γ$ if there exists a constant $ρ\u003e 0$ such that one row or column has exactly $\\lceil γn \\rceil$ entries with values at least $ρ$, and every other row and column has at least $\\lceil γn \\rceil$ such entries. For the upper bound, we show that the Sinkhorn-Knopp algorithm produces a nearly doubly stochastic matrix in $O(\\log n - \\log \\varepsilon)$ iterations and $\\widetilde{O}(n^2)$ time for all nonnegative square matrices whose normalized version has a density $γ\u003e 1/2$. Such matrices cover both the algorithm's principal practical inputs and its typical theoretical regime, and the $\\widetilde{O}(n^2)$ runtime is optimal. For the lower bound, we establish a tight bound of $\\widetildeΩ\\left(n^{1/2}/\\varepsilon\\right)$ iterations for positive matrices under the $\\ell_2$-norm error measure. Moreover, for every $γ\u003c 1/2$, there exists a matrix with density $γ$ for which the algorithm requires $Ω\\left(n^{1/2}/\\varepsilon\\right)$ iterations. In summary, our results reveal a sharp phase transition in the Sinkhorn-Knopp algorithm at the density threshold $γ= 1/2$.","short_abstract":"The matrix scaling problem, particularly the Sinkhorn-Knopp algorithm, has been studied for over 60 years. In practice, the algorithm often yields high-quality approximations within just a few iterations. Theoretically, however, the best-known upper bound places it in the class of pseudopolynomial-time approximation al...","url_abs":"https://arxiv.org/abs/2507.09711","url_pdf":"https://arxiv.org/pdf/2507.09711v2","authors":"[\"Kun He\"]","published":"2025-07-13T17:07:51Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}