Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor

Abstract

Consider the problem of computing the largest eigenvalue for nonnegative tensors. In this paper, we establish the Q-linear convergence of a power type algorithm for this problem under a weak irreducibility condition. Moreover, we present a convergent algorithm for calculating the largest eigenvalue for any nonnegative tensors.

Keywords

Eigenvalue / nonnegative tensor / power method / linear convergence

References

[1] Bloy L, Verma R. On computing the underlying fiber directions from the diffusion orientation distribution function. In: Medical Image Computing and Computer- Assisted Intervention MICCAI 2008. Berlin/Heidelberg: Springer, 2008, 1-8

[2] Bulò S R, Pelillo M. New bounds on the clique number of graphs based on spectral hypergraph theory. In: Sttzle Ts, ed. Learning and Intelligent Optimization. Berlin: Springer-Verlag, 2009, 45-48

[3] Chang K C, Pearson K, Zhang T. Perron-Frobenius theorem for nonnegative tensors. Commun Math Sci, 2008, 6: 507-520

[4] Chang K C, Pearson K, Zhang T. On eigenvalue problems of real symmetric tensors. J Math Anal Appl, 2009, 350: 416-422

[5] Chang K C, Pearson K, Zhang T. Primitivity, the convergence of the NQZ method, and the largest eigenvalue for nonnegative tensors. SIAM J Matrix Anal Appl, 2011, 32: 806-819

[6] Chang K C, Qi L, Zhou G. Singular values of a real rectangular tensor. J Math Anal Appl, 2010, 370: 284-294

[7] Collatz L. Einschliessungssatz für die charakteristischen Zahlen von Matrizen. Math Z, 1942, 48: 221-226

[8] De Lathauwer L, De Moor B, Vandewalle J. On the best rank-1 and rank-(R₁, ..., R_N) approximation of higher-order tensors. SIAM J Matrix Anal Appl, 2000, 21: 1324-1342

[9] Drineas P, Lim L-H. A multilinear spectral theory of hyper-graphs and expander hypergraphs. 2005

[10] Friedland S, Gaubert S, Han L. Perron-Frobenius theorem for nonnegative multilinear forms and extensions. Linear Algebra Appl, 2013, 438: 738-749

[11] Golub G H, Loan C F V. Matrix Computations. Baltimore: Johns Hopkins University Press, 1996

[12] Horn R A, Johnson C R. Matrix Analysis. Cambridge: Cambridge University Press, 1985

[13] Hu S, Huang Z, Qi L. Finding the spectral radius of a nonnegative tensor. Department of Applied Mathematics, The Hong Kong Polytechnic University, 2010

[14] Kofidis E, Regalia P A. On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM J Matrix Anal Appl, 2002, 23: 863-884

[15] Kolda T G, Bader B W. Tensor decompositions and applications. SIAM Rev, 2009, 51 455-500

[16] Lim L-H. Singular values and eigenvalues of tensors: a variational approach. In: Proceedings IEEE InternationalWorkshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP '05), Vol 1. 2005, 129-132

[17] Lim L-H. Multilinear pagerank: measuring higher order connectivity in linked objects. In: The Internet: Today and Tomorrow. <month>July</month>, 2005

[18] Liu Y, Zhou G, N. F. Ibrahim N F. An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor. J Comput Appl Math, 2010, 235: 286-292

[19] Minc H. Nonnegative Matrices. New York: John Wiley and Sons, Inc, 1988

[20] Ng M, Qi L, Zhou G. Finding the largest eigenvalue of a non-negative tensor. SIAM J Matrix Anal Appl, 2009, 31: 1090-1099

[21] Ni Q, Qi L, Wang F. An eigenvalue method for testing the positive definiteness of a multivariate form. IEEE Trans Automatic Control, 2008, 53: 1096-1107

[22] Pearson K J. Essentially positive tensors. Int J Algebra, 2010, 4: 421-427

[23] Qi L. Eigenvalues of a real supersymmetric tensor. J Symbolic Comput, 2005, 40: 1302-1324

[24] Qi L. The spectral theory of tensors. Department of Applied Mathematics, The Hong Kong Polytechnic University, 2012

[25] Qi L, Wang F, Wang Y. Z-eigenvalue methods for a global polynomial optimization problem. Math Program, 2009, 118: 301-316

[26] Qi L, Wang Y, Wu E X. D-eigenvalues of diffusion kurtosis tensor. J Comput Appl Math, 2008, 221: 150-157

[27] Shashua A, Hazan T. Non-negative tensor factorization with applications to statistics and computer vision. In: International Conference of Machine Learning (ICML), <month>August</month>, 2005

[28] Varga R. Matrix Iterative Analysis. Englewood Cliffs: Prentice-Hall, Inc, 1962

[29] Wood R J, O’ Neill M J. Finding the spectral radius of a large sparse non-negative matrix. ANZIAM J, 2007, 48: C330-C345

[30] Yang Y, Yang Q. Further results for Perron-Frobenius theorem for nonnegative tensors. SIAM J Matrix Anal Appl, 2010, 31: 2517-2530

[31] Zhang L, Qi L. Linear convergence of an algorithm for computing the largest eigenvalue of a nonnegative tensor. Numer Linear Algebra Appl, 2012, 19: 830-841

[32] Zhang L, Qi L, Xu Y. Finding the largest eigenvalue of an irreducible nonnegative tensor and linear convergence for weakly positive tensors. J Comput Math, 2012, 30: 24-33

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg