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.

Key words： 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