A fast algorithm for matrix balancing

Philip Knight, Daniel Ruiz

Research output: Contribution to journalArticle

88 Citations (Scopus)

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.
LanguageEnglish
Pages1029-1047
Number of pages19
JournalIMA Journal of Numerical Analysis
Volume33
Issue number3
Early online date26 Oct 2012
DOIs
Publication statusPublished - 2013

Fingerprint

Balancing
Fast Algorithm
Iteration
Preconditioned Conjugate Gradient Method
Conjugate gradient method
Quadratic Convergence
Iteration Scheme
Nonnegative Matrices
Square matrix
Iterative methods
Scaling
Sufficient
Converge
Costs
Family

Keywords

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

Cite this

Knight, Philip ; Ruiz, Daniel. / A fast algorithm for matrix balancing. In: IMA Journal of Numerical Analysis. 2013 ; Vol. 33, No. 3. pp. 1029-1047.
@article{de06599b7bf3486eb1c007a98c6acc95,
title = "A fast algorithm for matrix balancing",
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.",
keywords = "matrix balancing , quadratic convergence , diagonal scaling, Sinkhorn-Knopp algorithm, doubly stochastic matrix, conjugate gradient iteration",
author = "Philip Knight and Daniel Ruiz",
year = "2013",
doi = "10.1093/imanum/drs019",
language = "English",
volume = "33",
pages = "1029--1047",
journal = "IMA Journal of Numerical Analysis",
issn = "0272-4979",
number = "3",

}

A fast algorithm for matrix balancing. / Knight, Philip; Ruiz, Daniel.

In: IMA Journal of Numerical Analysis, Vol. 33, No. 3, 2013, p. 1029-1047.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A fast algorithm for matrix balancing

AU - Knight, Philip

AU - Ruiz, Daniel

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - matrix balancing

KW - quadratic convergence

KW - diagonal scaling

KW - Sinkhorn-Knopp algorithm

KW - doubly stochastic matrix

KW - conjugate gradient iteration

U2 - 10.1093/imanum/drs019

DO - 10.1093/imanum/drs019

M3 - Article

VL - 33

SP - 1029

EP - 1047

JO - IMA Journal of Numerical Analysis

T2 - IMA Journal of Numerical Analysis

JF - IMA Journal of Numerical Analysis

SN - 0272-4979

IS - 3

ER -