Accelerating the Sinkhorn-Knopp iteration by Arnoldi-type methods

DOI10.1007/S10092-020-0359-7zbMATH Open1437.65015arXiv1810.09700OpenAlexW3006466045MaRDI QIDQ2174200FDOQ2174200

Authors: A. Aristodemo, L. Gemignani 

Publication date: 21 April 2020

Published in: Calcolo (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (3)

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

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)