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. Medical Image Computing and Computer-Assisted Intervention MICCAI 2008, 2008, Berlin/Heidelberg: Springer 1 8

[2.] Bulò S. R., Pelillo M.. Stützle T.. New bounds on the clique number of graphs based on spectral hypergraph theory. Learning and Intelligent Optimization, 2009, Berlin: Springer-Verlag 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₁, h.,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, 1996, Baltimore: Johns Hopkins University Press

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

[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. July, 2005

[18.] Liu Y., Zhou G., Zhou 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, 1988, New York: John Wiley and Sons, Inc

[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), August, 2005

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

[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