A Fast Algorithm for Matrix Balancing

By Philip A. Knight, Daniel Ruiz. Web Information Retrieval and Linear Algebra Algorithms, 2013

517 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/4f5d26b58c3ad6697bada5553496c62fc2a91295

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

A review of matrix scaling and Sinkhorn's normal form for matrices and positive maps (2016, methodology): “They can either be seen as Newton’s method applied to xT Ax for symmetric A (cf. Khachiyan and Kalantari 1992) or as Newton’s method applied to the Sinkhorn iteration equation xk+1 := e/(Axk) (cf. Knight and Ruiz 2012).”
Learning with a Wasserstein Loss (2015, background): “This cost can be prohibitive when optimizing by gradient descent.”
Genome-wide mapping and analysis of chromosome architecture (2016, methodology): “Meanwhile, a fast version of the matrix-balancing Sinkhorn–Knopp algorithm 82 , originally described by Knight and Ruiz 83 , has been applied to account for biases in the finest resolution Hi-C data sets 27 (TABLE 3) .”
Juicer provides a one-click system for analyzing loop-resolution Hi-C experiments (2016, unknown): “The options include our original normalization scheme (Lieberman-Aiden et al., 2009), aswell as amatrix balancing scheme that ensures that each row and column of the contact matrix sums to the same value (Knight and Ruiz, 2012).”
Galaxy HiCExplorer 3: a web server for reproducible Hi-C, capture Hi-C and single-cell Hi-C data analysis, quality control and visualization (2020, methodology): “Imakaev (31), HiCExplorer also offers the Knight-Ruiz correction (32), first used for Hi-C matrices by (9).”
Fast Computation of Wasserstein Barycenters (2013, methodology): “…linear when us-ing Hilbert’s projective metric between the scaling factors (Franklin and Lorenz, 1989, § 3). because Although we use this al-gorithm in our experiments of its simplicity, other algorithms exist (Knight and Ruiz, 2012) which are known to be more reliable numerically when λ is large.”
A three-dimensional map of the human genome at kilobase resolution reveals principles of chromatin looping (2014, unknown): “Normalized contact matrices are produced at all resolutions using Knight and Ruiz (2012).”