Methods for Scaling to Doubly Stochastic Form,

Abstract

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 26, 1981
Accession Number
ADA102570

Entities

People

  • Beresford N. Parlett
  • T. L. Landis

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algebra
  • Algorithms
  • Applied Mathematics
  • Arithmetic
  • Computer Science
  • Convergence
  • Equations
  • Inequalities
  • Iterations
  • Markov Chains
  • Mathematics
  • Military Research
  • Permutations
  • Precision
  • Sequences
  • Test Beds

Readers

  • Approximation Theory.
  • Linear Algebra
  • Statistical inference.