Methods for Scaling to Doubly Stochastic Form

摘要

New methods for scaling square, nonnegative matrices to doubly stochastic form are described. A generalized version of the convergence theorem in SINKHORN and KNOPP 1967 is proved and applied to show convergence for these new methods. Tests indicate that one of the new methods has significantly better average and worst-case behavior than the Sinkhorn/Knopp methods; for one of the 3X3 examples in MARSHALL and OLKIN 1968, SK requires 130 times as many operations as the new algorithm to achieve row and column sums 1+or-10 to the minus 5th power. (Author)