Accelerating the Sinkhorn-Knopp iteration by Arnoldi-type methods

DOI10.1007/S10092-020-0359-7MaRDI QIDQ2174200zbMATHOpenAlexFDO

Authors A. Aristodemo, L. Gemignani

Publication date 21 April 2020

Published in Calcolo (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.09700

zbMATH Keywords

nonlinear eigenvalue problemArnoldi methodpower methodSinkhorn-Knopp iteration

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical solution of nonlinear eigenvalue and eigenvector problems (65H17)

Abstract: It is shown that the problem of balancing a nonnegative matrix by positive diagonal matrices can be recast as a constrained nonlinear multiparameter eigenvalue problem. Based on this equivalent formulation some adaptations of the power method and Arnoldi process are proposed for computing the dominant eigenvector which defines the structure of the diagonal transformations. Numerical results illustrate that our novel methods accelerate significantly the convergence of the customary Sinkhorn-Knopp iteration for matrix balancing in the case of clustered dominant eigenvalues.

Recommendations

• A fast algorithm for matrix balancing
• Interval-constrained matrix balancing
• The Sinkhorn–Knopp Algorithm: Convergence and Applications
• Permanents, \(\alpha\)-permanents and Sinkhorn balancing
• A Symmetry Preserving Algorithm for Matrix Scaling

Cites work

• scientific article; zbMATH DE number 3574935 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 3204642 (Why is no real title available?)
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• A fast algorithm for matrix balancing
• Aggregation of Variables in Dynamic Systems
• An Arnoldi-type algorithm for computing Page Rank
• An Inverse Iteration Method for Eigenvalue Problems with Eigenvector Nonlinearities
• Augmented block Householder Arnoldi method
• Concerning nonnegative matrices and doubly stochastic matrices
• Convergence of the iterative proportional fitting procedure
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• Further analysis of the Arnoldi process for eigenvalue problems
• Generalizations of the Frobenius-Wielandt Theorems for Non-Negative Square Matrices
• Methods for scaling to doubly stochastic form
• Near-Decomposability, Partition and Aggregation, and the Relevance of Stability Discussions
• Nearly decomposable matrices
• Nonlinear Perron-Frobenius theory
• On an Eigenvector-Dependent Nonlinear Eigenvalue Problem
• On the Complexity of Matrix Balancing
• On the powers of a matrix with perturbations
• Practical acceleration for computing the HITS expertrank vectors
• Robust Rayleigh quotient minimization and nonlinear eigenvalue problems
• Some Spectral Properties of an Operator Associated with a Pair of Nonnegative Matrices
• Stochastic data clustering
• Stochastic matrix-free equilibration
• Templates for the Solution of Algebraic Eigenvalue Problems
• The Sinkhorn–Knopp Algorithm: Convergence and Applications
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• The spectrum of a nonlinear operator associated with a matrix

Cited in

(3)

• The Sinkhorn–Knopp Algorithm: Convergence and Applications
• A low cost Arnoldi method for large linear initial value problems
• Matrix-free \(W\)-methods using a multiple Arnoldi iteration

Describes a project that uses

Uses Software

• JDQR
• JDQZ

This page was built for publication: Accelerating the Sinkhorn-Knopp iteration by Arnoldi-type methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174200)