# Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling

arXiv: https://arxiv.org/abs/1801.02790 · HTML: https://mlsanity.com/paper/1801.02790/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jan 2018.

## Built on by (most cited first, 14 of 14)

- [mHC-lite: You Don't Need 20 Sinkhorn-Knopp Iterations](https://mlsanity.com/paper/2601.05732/) (2026)
- [LinSATNet: The Positive Linear Satisfiability Neural Networks](https://mlsanity.com/paper/2407.13917/) (2024)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples](https://mlsanity.com/paper/2103.00394/) (2021)
- [GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent](https://mlsanity.com/paper/2409.17500/) (2024)
- [On Sinkhorn's Algorithm and Choice Modeling](https://mlsanity.com/paper/2310.00260/) (2023)
- [Discrete Optimal Transport with Independent Marginals is #P-Hard](https://mlsanity.com/paper/2203.01161/) (2022)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [Differentiable Cluster Graph Neural Network](https://mlsanity.com/paper/2405.16185/) (2024)
- [Phase transition of the Sinkhorn-Knopp algorithm](https://mlsanity.com/paper/2507.09711/) (2025)
- [Robust Sublinear Convergence Rates for Iterative Bregman Projections](https://mlsanity.com/paper/2602.01372/) (2026)
- [Efficient Optimal Transport Algorithm by Accelerated Gradient descent](https://mlsanity.com/paper/2104.05802/) (2021)
- [A Class of Topological Pseudodistances for Fast Comparison of Persistence Diagrams](https://mlsanity.com/paper/2402.14489/) (2024)
- [Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp](https://mlsanity.com/paper/2608.11760/) (2026)

## Abstract (arXiv)

Given a non-negative n × m real matrix A, the em matrix scaling problem is to determine if it is possible to scale the rows and columns so that each row and each column sums to a specified target value for it. This problem arises in many algorithmic applications, perhaps most notably as a preconditioning step in solving a linear system of equations. One of the most natural and by now classical approach to matrix scaling is the Sinkhorn-Knopp algorithm (also known as the RAS method) where one alternately scales either all rows or all columns to meet the target values. In addition to being extremely simple and natural, another appeal of this procedure is that it easily lends itself to parallelization. A central question is to understand the rate of convergence of the Sinkhorn-Knopp algorithm. In this paper, we present an elementary convergence analysis for the Sinkhorn-Knopp algorithm that improves upon the previous best bound. In a nutshell, our approach is to show a simple bound on the number of iterations needed so that the KL-divergence between the current row-sums and the target row-sums drops below a specified threshold δ, and then connect the KL-divergence with ℓ1 and ℓ2 distances. For ℓ1, we can use Pinsker's inequality. For ℓ2, we develop a strengthening of Pinsker's inequality, called (KL vs ℓ1/ℓ2) in the paper, which lower bounds the KL-divergence by a combination of ℓ1 and ℓ2 distance. This inequality may be of independent interest. The idea of studying Sinkhorn-Knopp convergence via KL-divergence is not new and has indeed been previously explored. Our contribution is an elementary, self-contained presentation of this approach and an interesting new inequality that yields a significantly stronger convergence guarantee for the extensively studied ℓ2-error.