# Much Faster Algorithms for Matrix Scaling

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Apr 2017.

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

- [Discrete Copula Diffusion](https://mlsanity.com/paper/2410.01949/) (2024)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling](https://mlsanity.com/paper/2209.08004/) (2022)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)
- [Entropic Optimal Transport Eigenmaps for Nonlinear Alignment and Joint Embedding of High-Dimensional Datasets](https://mlsanity.com/paper/2407.01718/) (2024)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [On a class of geodesically convex optimization problems solved via Euclidean MM methods](https://mlsanity.com/paper/2206.11426/) (2022)
- [Phase transition of the Sinkhorn-Knopp algorithm](https://mlsanity.com/paper/2507.09711/) (2025)
- [Efficient Discretizations of Optimal Transport](https://mlsanity.com/paper/2102.07956/) (2021)
- [Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp](https://mlsanity.com/paper/2608.11760/) (2026)

## Abstract (arXiv)

We develop several efficient algorithms for the classical Matrix Scaling problem, which is used in many diverse areas, from preconditioning linear systems to approximation of the permanent. On an input n× n matrix A, this problem asks to find diagonal (scaling) matrices X and Y (if they exist), so that X A Y varepsilon-approximates a doubly stochastic, or more generally a matrix with prescribed row and column sums. We address the general scaling problem as well as some important special cases. In particular, if A has m nonzero entries, and if there exist X and Y with polynomially large entries such that X A Y is doubly stochastic, then we can solve the problem in total complexity tildeO(m + n4/3). This greatly improves on the best known previous results, which were either tildeO(n4) or O(m n1/2/varepsilon). Our algorithms are based on tailor-made first and second order techniques, combined with other recent advances in continuous optimization, which may be of independent interest for solving similar problems.