# Stochastic Matrix-Free Equilibration

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2016.

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

- [Restricted Dynamic Geometric Complexity: Path-Space Reduction and M"obius--Jacobi Response](https://mlsanity.com/paper/2607.07204/) (2026)
- [Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp](https://mlsanity.com/paper/2608.11760/) (2026)

## Abstract (arXiv)

We present a novel method for approximately equilibrating a matrix A ∈ bf Rm × n using only multiplication by A and AT. Our method is based on convex optimization and projected stochastic gradient descent, using an unbiased estimate of a gradient obtained by a randomized method. Our method provably converges in expectation with an O(1/t) convergence rate and empirically gets good results with a small number of iterations. We show how the method can be applied as a preconditioner for matrix-free iterative algorithms such as LSQR and Chambolle-Cremers-Pock, substantially reducing the iterations required to reach a given level of precision. We also derive a novel connection between equilibration and condition number, showing that equilibration minimizes an upper bound on the condition number over all choices of row and column scalings.