nach oben

Calcolo

Erschienen in:

01.03.2020

Accelerating the Sinkhorn–Knopp iteration by Arnoldi-type methods

verfasst von: A. Aristodemo, L. Gemignani

Erschienen in: Calcolo | Ausgabe 1/2020

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Tensor-Train decomposition for image recognition

Nächster Artikel On norm compression inequalities for partitioned block tensors

For complexity comparisons the term ‘convergence rate’ here and hereafter denotes the reciprocal of the usual convergence rate and it is roughly the number of iterations required to attain a error tolerance of \(1.0\mathrm{e}{-}1\).

Ando, A., Fisher, F.M.: Near-decomposability, partition and aggregation, and the relevance of stability discussions. Int. Econ. Rev. 4(1), 53–67 (1963)CrossRef

Baglama, J.: Augmented block householder Arnoldi method. Linear Algebra Appl. 429(10), 2315–2334 (2008)MathSciNetCrossRef

Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., van der Vorst, H. (eds.): Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Volume 11 of Software, Environments, and Tools. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2000)

Bai, Z., Lu, D., Vandereycken, B.: Robust Rayleigh quotient minimization and nonlinear eigenvalue problems. SIAM J. Sci. Comput. 40(5), A3495–A3522 (2018)MathSciNetCrossRef

Bellalij, M., Saad, Y., Sadok, H.: Further analysis of the Arnoldi process for eigenvalue problems. SIAM J. Numer. Anal. 48(2), 393–407 (2010)MathSciNetCrossRef

Bozzo, E., Franceschet, M.: A theory on power in networks. Commun. ACM 59(11), 75–83 (2016)CrossRef

Brualdi, R.A., Parter, S.V., Schneider, H.: The diagonal equivalence of a nonnegative matrix to a stochastic matrix. J. Math. Anal. Appl. 16, 31–50 (1966)MathSciNetCrossRef

Cai, Y., Zhang, L.H., Bai, Z., Li, R.C.: On an eigenvector-dependent nonlinear eigenvalue problem. SIAM J. Matrix Anal. Appl. 39(3), 1360–1382 (2018)MathSciNetCrossRef

Courtois, P.-J.: Decomposability: Queueing and Computer System Applications. ACM Monograph Series. Academic Press, New York (1977)

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)MathSciNetCrossRef

13.

Gleiser, P.M., Danon, L.: Community structure in jazz. Adv. Complex Syst. 6(4), 565–573 (2003)CrossRef

14.

Golub, G.H., Greif, C.: An Arnoldi-type algorithm for computing PageRank. BIT 46(4), 759–771 (2006)MathSciNetCrossRef

15.

Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences, 4th edn. Johns Hopkins University Press, Baltimore (2013)

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)MathSciNetCrossRef

18.

Kalantari, B., Khachiyan, L., Shokoufandeh, A.: On the complexity of matrix balancing. SIAM J. Matrix Anal. Appl. 18(2), 450–463 (1997)MathSciNetCrossRef

19.

Knight, P.A.: The Sinkhorn–Knopp algorithm: convergence and applications. SIAM J. Matrix Anal. Appl. 30(1), 261–275 (2008)MathSciNetCrossRef

20.

Knight, P.A., Ruiz, D.: A fast algorithm for matrix balancing. IMA J. Numer. Anal. 33(3), 1029–1047 (2013)MathSciNetCrossRef

21.

Lamond, B., Stewart, N.F.: Bregman’s balancing method. Transp. Res. B 15(4), 239–248 (1981)MathSciNetCrossRef

22.

Lemmens, B., Nussbaum, R.: Nonlinear Perron–Frobenius Theory. Cambridge Tracts in Mathematics, vol. 189. Cambridge University Press, Cambridge (2012)CrossRef

23.

Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities. Dover Publications, Inc., New York (1992). (reprint of the 1969 edition)MATH

24.

Menon, M.V.: Some spectral properties of an operator associated with a pair of nonnegative matrices. Trans. Am. Math. Soc. 132, 369–375 (1968)MathSciNetCrossRef

25.

Menon, M.V., Schneider, H.: The spectrum of a nonlinear operator associated with a matrix. Linear Algebra Appl. 2, 321–334 (1969)MathSciNetCrossRef

26.

Meyer, C.D., Wessell, C.D.: Stochastic data clustering. SIAM J. Matrix Anal. Appl. 33(4), 1214–1236 (2012)MathSciNetCrossRef

27.

Minc, H.: Nearly decomposable matrices. Linear Algebra Appl. 5, 181–187 (1972)MathSciNetCrossRef

28.

Morishima, M.: Generalizations of the Frobenius–Wielandt theorems for non-negative square matrices. J. Lond. Math. Soc. 36, 211–220 (1961)MathSciNetCrossRef

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)CrossRef

31.

Parlett, B.N., Landis, T.L.: Methods for scaling to doubly stochastic form. Linear Algebra Appl. 48, 53–79 (1982)MathSciNetCrossRef

32.

Rüschendorf, L.: Convergence of the iterative proportional fitting procedure. Ann. Stat. 23(4), 1160–1174 (1995)MathSciNetCrossRef

33.

Simon, H.A., Ando, A.: Aggregation of variables in dynamic systems. Econometrica 29(2), 111–138 (1961)CrossRef

34.

Sinkhorn, R.: A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Stat. 35, 876–879 (1964)MathSciNetCrossRef

35.

Sinkhorn, R.: Diagonal equivalence to matrices with prescribed row and column sums. Am. Math. Monthly 74, 402–405 (1967)MathSciNetCrossRef

36.

Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pac. J. Math. 21, 343–348 (1967)MathSciNetCrossRef

37.

Stewart, G.W.: On the powers of a matrix with perturbations. Numer. Math. 96(2), 363–376 (2003)MathSciNetCrossRef

38.

Zhou, Y.: Practical acceleration for computing the HITS ExpertRank vectors. J. Comput. Appl. Math. 236(17), 4398–4409 (2012)MathSciNetCrossRef

Titel: Accelerating the Sinkhorn–Knopp iteration by Arnoldi-type methods
verfasst von: A. Aristodemo
L. Gemignani
Publikationsdatum: 01.03.2020
Verlag: Springer International Publishing
Erschienen in: Calcolo / Ausgabe 1/2020
Print ISSN: 0008-0624
Elektronische ISSN: 1126-5434
DOI: https://doi.org/10.1007/s10092-020-0359-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 1/2020

Tensor-Train decomposition for image recognition

Odd and Even Lidstone-type polynomial sequences. Part 2: applications

An augmented fully-mixed finite element method for a coupled flow-transport problem

Full discretization of time dependent convection–diffusion–reaction equation coupled with the Darcy system

Preconditioned iterative method for boundary value method discretizations of a parabolic optimal control problem

Stabilizing the Metzler matrices with applications to dynamical systems