A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps

By Martin Idel. 2016

148 citations recorded by the source corpus.

Given a nonnegative matrix $A$, can you find diagonal matrices $D_1,~D_2$ such that $D_1AD_2$ is doubly stochastic? The answer to this question is known as Sinkhorn's theorem. It has been proved with a wide variety of methods, each presenting a variety of possible generalisations. Recently, generalisations such as to positive maps between matrix algebras have become more and more interesting for applications. This text gives a review of over 70 years of matrix scaling. The focus lies on the mathematical landscape surrounding the problem and its solution as well as the generalisation to positive maps and contains hardly any nontrivial unpublished results.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Numerical Analysis

How researchers see this paper

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

In Computational Theory and Mathematics

In Geometry and Topology

In Numerical Analysis

Citations in the corpus

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “This problem has been applied in image reconstruction, operations research, decision and control, and other scientific disciplines (see survey [20]).”
Computational Optimal Transport (2018, methodology): “There also exists an equivalent of Sinkhorn’s algorithm, which is due to Gurvits [2004] and has been extensively studied in [Georgiou and Pavon, 2015]; see also the review paper [Idel, 2016].”
Much Faster Algorithms for Matrix Scaling (2017, unknown): “For more references, we refer the reader to the survey [15], the paper [33] and references therein.”
News and uncertainty about COVID-19: Survey evidence and short-run economic impact (2020, methodology): “To do so, we apply iterative proportional fitting to create respondent weights after completion of the survey (“raking,” see, for example, Bishop et al. (1975) or Idel (2016) ).”
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods (2017, background): “The literature on these problems [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15] is truly extensive and dates back to 1960s.”