Much Faster Algorithms for Matrix Scaling

By Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson. 2017

123 citations recorded by the source corpus.

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 ε-approximates a doubly stochastic matrix, 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 \tilde{O}(m + n^{4/3}). This greatly improves on the best known previous results, which were either \tilde{O}(n^4) or O(m n^{1/2}/ε).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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “2 In matrix scaling [7, 10], given a non-negative matrix, one wants to re-scale its rows and columns to make it doubly stochastic.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “More careful use of linear coupling can also give accelerated methods for non-smooth problems (such as positive LP [8, 9], positive SDP [3], matrix scaling [6]) or for general non-convex problems [2].”
How To Make the Gradients Small Stochastically (2018, background): “” Another example is matrix scaling [4, 7], where given a non-negative matrix A ∈ Rn×m, we want to find positive diagonal matrices X ∈ Rn×n, Y ∈ Rm×m such that XAY is close to being doubly-stochastic.”
Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm (2018, background): “While the entropy-regularized OT problem allows to use other matrix-scaling algorithms such as (Allen-Zhu et al., 2017; Cohen et al., 2017) with theoretical guarantees, the authors do not provide any experimental re-sults, so the practical implementability of these algorithms is questionable.”
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration (2017, background): “As a result, recent work showing that Π S ( A, U r,c ) can be approximated in near-linear time [AZLOW17, CMTV17] has bypassed the Sinkhorn-Knopp algorithm entirely.”
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods (2017, result): “Finally, Linial, Samorodnitsky, and Wigderson [33] gave an Õ(n7 log(1/ε)) time algorithm that is also strongly polynomial, in the sense that it does not depend at all on the size of input entries.”