A fast algorithm for matrix balancing

Philip Knight, Daniel Ruiz

Research output: Contribution to journalArticle

120 Citations (Scopus)
568 Downloads (Pure)

Abstract

As long as a square nonnegative matrix A contains sufficient nonzero elements, then the matrix can be balanced, that is we can find a diagonal scaling of A that is doubly stochastic. A number of algorithms have been proposed to achieve the balancing, the most well known of these being Sinkhorn-Knopp. In this paper we derive new algorithms based on inner-outer iteration schemes. We show that Sinkhorn-Knopp belongs to this family, but other members can converge much more quickly. In particular, we show that while stationary iterative methods offer little or no improvement in many cases, a scheme using a preconditioned conjugate gradient method as the inner iteration can give quadratic convergence at low cost.
Original languageEnglish
Pages (from-to)1029-1047
Number of pages19
JournalIMA Journal of Numerical Analysis
Volume33
Issue number3
Early online date26 Oct 2012
DOIs
Publication statusPublished - 2013

Keywords

  • matrix balancing
  • quadratic convergence
  • diagonal scaling
  • Sinkhorn-Knopp algorithm
  • doubly stochastic matrix
  • conjugate gradient iteration

Fingerprint Dive into the research topics of 'A fast algorithm for matrix balancing'. Together they form a unique fingerprint.

  • Cite this