Accelerating the Sinkhorn-Knopp iteration by Arnoldi-type methods.(English)Zbl 1437.65015

Summary: It is shown that the problem of balancing a nonnegative matrix by positive diagonal matrices can be recast as a nonlinear eigenvalue problem with eigenvector nonlinearity. 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.

MSC:

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

JDQZ; JDQR
Full Text:

References:

 [1] Ando, A.; Fisher, Fm, Near-decomposability, partition and aggregation, and the relevance of stability discussions, Int. Econ. Rev., 4, 1, 53-67 (1963) · Zbl 0121.15104 [2] Baglama, J., Augmented block householder Arnoldi method, Linear Algebra Appl., 429, 10, 2315-2334 (2008) · Zbl 1153.65034 [3] Bai, Z.; Demmel, J.; Dongarra, J.; Ruhe, A.; Van Der Vorst, H., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Volume 11 of Software, Environments, and Tools (2000), Philadelphia: Society for Industrial and Applied Mathematics (SIAM), Philadelphia · Zbl 0965.65058 [4] Bai, Z.; Lu, D.; Vandereycken, B., Robust Rayleigh quotient minimization and nonlinear eigenvalue problems, SIAM J. Sci. Comput., 40, 5, A3495-A3522 (2018) · Zbl 1416.65148 [5] Bellalij, M.; Saad, Y.; Sadok, H., Further analysis of the Arnoldi process for eigenvalue problems, SIAM J. Numer. Anal., 48, 2, 393-407 (2010) · Zbl 1210.65085 [6] Bozzo, E.; Franceschet, M., A theory on power in networks, Commun. ACM, 59, 11, 75-83 (2016) [7] Brualdi, Ra; Parter, Sv; Schneider, H., The diagonal equivalence of a nonnegative matrix to a stochastic matrix, J. Math. Anal. Appl., 16, 31-50 (1966) · Zbl 0231.15017 [8] Cai, Y.; Zhang, Lh; Bai, Z.; Li, Rc, On an eigenvector-dependent nonlinear eigenvalue problem, SIAM J. Matrix Anal. Appl., 39, 3, 1360-1382 (2018) · Zbl 1401.65036 [9] Courtois, P-J, Decomposability: Queueing and Computer System Applications. ACM Monograph Series (1977), New York: Academic Press, New York · Zbl 0368.68004 [10] Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Advances in Neural Information Processing Systems (NIPS) 26, pp. 2292-2300. MIT Press, Cambridge, MA (2013) [11] De Sa, C.; He, B.; Mitliagkas, I.; Ré, C.; Xu, P., Accelerated stochastic power iteration, Proc. Mach. Learn. Res., 84, 58-67 (2018) [12] Diamond, S.; Boyd, S., Stochastic matrix-free equilibration, J. Optim. Theory Appl., 172, 2, 436-454 (2017) · Zbl 1367.65068 [13] Gleiser, Pm; Danon, L., Community structure in jazz, Adv. Complex Syst., 6, 4, 565-573 (2003) [14] Golub, Gh; Greif, C., An Arnoldi-type algorithm for computing PageRank, BIT, 46, 4, 759-771 (2006) · Zbl 1105.65034 [15] Golub, Gh; Van Loan, Cf, Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences (2013), Baltimore: Johns Hopkins University Press, Baltimore [16] Idel, M.: A review of matrix scaling and Sinkhorn’s normal form for matrices and positive maps. Technical report (2016). arXiv:1609.06349 [17] Jarlebring, E.; Kvaal, S.; Michiels, W., An inverse iteration method for eigenvalue problems with eigenvector nonlinearities, SIAM J. Sci. Comput., 36, 4, A1978-A2001 (2014) · Zbl 1307.65068 [18] Kalantari, B.; Khachiyan, L.; Shokoufandeh, A., On the complexity of matrix balancing, SIAM J. Matrix Anal. Appl., 18, 2, 450-463 (1997) · Zbl 0882.65031 [19] Knight, Pa, The Sinkhorn-Knopp algorithm: convergence and applications, SIAM J. Matrix Anal. Appl., 30, 1, 261-275 (2008) · Zbl 1166.15301 [20] Knight, Pa; Ruiz, D., A fast algorithm for matrix balancing, IMA J. Numer. Anal., 33, 3, 1029-1047 (2013) · Zbl 1276.65025 [21] Lamond, B.; Stewart, Nf, Bregman’s balancing method, Transp. Res. B, 15, 4, 239-248 (1981) [22] Lemmens, B.; Nussbaum, R., Nonlinear Perron-Frobenius Theory. Cambridge Tracts in Mathematics (2012), Cambridge: Cambridge University Press, Cambridge · Zbl 1246.47001 [23] Marcus, M.; Minc, H., A Survey of Matrix Theory and Matrix Inequalities (1992), New York: Dover Publications, Inc., New York · Zbl 0126.02404 [24] Menon, Mv, Some spectral properties of an operator associated with a pair of nonnegative matrices, Trans. Am. Math. Soc., 132, 369-375 (1968) · Zbl 0169.35105 [25] Menon, Mv; Schneider, H., The spectrum of a nonlinear operator associated with a matrix, Linear Algebra Appl., 2, 321-334 (1969) · Zbl 0183.30902 [26] Meyer, Cd; Wessell, Cd, Stochastic data clustering, SIAM J. Matrix Anal. Appl., 33, 4, 1214-1236 (2012) · Zbl 1301.62067 [27] Minc, H., Nearly decomposable matrices, Linear Algebra Appl., 5, 181-187 (1972) · Zbl 0235.05008 [28] Morishima, M., Generalizations of the Frobenius-Wielandt theorems for non-negative square matrices, J. Lond. Math. Soc., 36, 211-220 (1961) · Zbl 0104.01301 [29] $$N \iota \kappa$$ o $$\lambda \alpha \kappa$$ ó $$\pi$$ o $$\upsilon \lambda$$ o $$\varsigma$$, A.N.: Ranking under near decomposability. Ph.D. thesis, Department of Computer Engineering and Informatics, University of Patras (2016) [30] Parikh, A., Forecasts of input-output matrices using the R.A.S. method, Rev. Econ. Stat., 61, 3, 477-481 (1979) [31] Parlett, Bn; Landis, Tl, Methods for scaling to doubly stochastic form, Linear Algebra Appl., 48, 53-79 (1982) · Zbl 0508.15003 [32] Rüschendorf, L., Convergence of the iterative proportional fitting procedure, Ann. Stat., 23, 4, 1160-1174 (1995) · Zbl 0851.62038 [33] Simon, Ha; Ando, A., Aggregation of variables in dynamic systems, Econometrica, 29, 2, 111-138 (1961) · Zbl 0121.15103 [34] Sinkhorn, R., A relationship between arbitrary positive matrices and doubly stochastic matrices, Ann. Math. Stat., 35, 876-879 (1964) · Zbl 0134.25302 [35] Sinkhorn, R., Diagonal equivalence to matrices with prescribed row and column sums, Am. Math. Monthly, 74, 402-405 (1967) · Zbl 0166.03702 [36] Sinkhorn, R.; Knopp, P., Concerning nonnegative matrices and doubly stochastic matrices, Pac. J. Math., 21, 343-348 (1967) · Zbl 0152.01403 [37] Stewart, Gw, On the powers of a matrix with perturbations, Numer. Math., 96, 2, 363-376 (2003) · Zbl 1089.15028 [38] Zhou, Y., Practical acceleration for computing the HITS ExpertRank vectors, J. Comput. Appl. Math., 236, 17, 4398-4409 (2012) · Zbl 1287.65027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.