Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.09711 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916889494552576 |
|---|---|
| author | He, Kun |
| author_facet | He, Kun |
| contents | 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 $ρ> 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 $γ> 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 $γ< 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09711 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Phase transition of the Sinkhorn-Knopp algorithm He, Kun Data Structures and Algorithms Machine Learning 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 $ρ> 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 $γ> 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 $γ< 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$. |
| title | Phase transition of the Sinkhorn-Knopp algorithm |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2507.09711 |