Sinkhorn's Theorem

Sinkhorn's theorem states that every square matrix with positive entries can be written in a certain standard form.

Theorem

If ''A'' is an ''n'' × ''n'' matrix with strictly positive elements, then there exist diagonal matrices ''D''₁ and ''D''₂ with strictly positive diagonal elements such that ''D''₁''AD''₂ is doubly stochastic. The matrices ''D''₁ and ''D''₂ are unique modulo multiplying the first matrix by a positive number and dividing the second one by the same number.Sinkhorn, Richard. (1964). "A relationship between arbitrary positive matrices and doubly stochastic matrices." ''Ann. Math. Statist.'' 35, 876–879.
Marshall, A.W., & Olkin, I. (1967). "Scaling of matrices to achieve specified row and column sums." ''Numerische Mathematik''. 12(1), 83–90.

Sinkhorn–Knopp algorithm

A simple iterative method to approach the double stochastic matrix is to alternately rescale all rows and all columns of ''A'' to sum to 1. Sinkhorn and Knopp presented this algorithm and analyzed its convergence.Sinkhorn, Richard, & Knopp, Paul. (1967). "Concerning nonnegative matrices and doubly stochastic matrices". ''Pacific J. Math.'' 21, 343–348.
This is essentially the same as the Iterative proportional fitting algorithm, well known in survey statistics.

Analogues and extensions

The following analogue for unitary matrices is also true: for every unitary matrix ''U'' there exist two diagonal unitary matrices ''L'' and ''R'' such that ''LUR'' has each of its columns and rows summing to 1.

The following extension to maps between matrices is also true (see Theorem 5 and also Theorem 4.7): given a Kraus operator
that represents the quantum operation Φ mapping a density matrix into another,
:$S \mapsto \Phi(S) = \sum_i B_i S B_i^*,$
that is trace preserving,
:$\sum_i B_i^* B_i = I,$
and, in addition, whose range is in the interior of the positive definite cone (strict positivity), there exist scalings ''x''_''j'', for ''j'' in , that are positive definite so that the rescaled Kraus operator
:$S \mapsto x_1\Phi(x_0^Sx_0^)x_1 = \sum_i (x_1B_ix_0^) S (x_1B_ix_0^)^*$
is doubly stochastic. In other words, it is such that both,
:$x_1\Phi(x_0^I x_0^)x_1 = I,$
as well as for the adjoint,
:$x_0^\Phi^*(x_1I x_1)x_0^ = I,$
where I denotes the identity operator.

Applications

In the 2010s Sinkhorn's theorem came to be used to find solutions of entropy-regularised optimal transport problems. This has been of interest in machine learning because such "Sinkhorn distances" can be used to evaluate the difference between data distributions and permutations. This improves the training of machine learning algorithms, in situations where maximum likelihood training may not be the best method.

References

{{DEFAULTSORT:Sinkhorn's Theorem
Matrix theory
Theorems in linear algebra