Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor

doi:10.1007/s11464-012-0268-4

Front Math Chin

2013, Vol. 8

Issue (1) : 155-168 https://doi.org/10.1007/s11464-012-0268-4

RESEARCH ARTICLE

Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor

Guanglu ZHOU¹(

), Liqun QI², Soon-Yi WU³

1. Department of Mathematics and Statistics, Curtin University, Perth, Australia; 2. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China; 3. Institute of Applied Mathematics, Cheng-Kung University, Tainan, China

Download: PDF(137 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): ZHOU Guanglu,Email:G.Zhou@curtin.edu.au

Issue Date: 01 February 2013

Cite this article:

Guanglu ZHOU,Liqun QI,Soon-Yi WU. Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor[J]. Front Math Chin, 2013, 8(1): 155-168.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-012-0268-4
https://academic.hep.com.cn/fmc/EN/Y2013/V8/I1/155

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 doi: 10.1007/978-3-540-85988-8_1
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 doi: 10.1007/978-3-642-11169-3_4
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 doi: 10.1016/j.jmaa.2008.09.067
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 doi: 10.1137/100807120
6	Chang K C, Qi L, Zhou G. Singular values of a real rectangular tensor. J Math Anal Appl , 2010, 370: 284-294 doi: 10.1016/j.jmaa.2010.04.037
7	Collatz L. Einschliessungssatz für die charakteristischen Zahlen von Matrizen. Math Z, 1942, 48: 221-226 doi: 10.1007/BF01180013
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 doi: 10.1137/S0895479898346995
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 doi: 10.1016/j.laa.2011.02.042
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 doi: 10.1137/S0895479801387413
15	Kolda T G, Bader B W. Tensor decompositions and applications. SIAM Rev , 2009, 51 455-500 doi: 10.1137/07070111X
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, 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 doi: 10.1016/j.cam.2010.06.002
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 doi: 10.1137/09074838X
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 doi: 10.1109/TAC.2008.923679
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 doi: 10.1016/j.jsc.2005.05.007
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 doi: 10.1007/s10107-007-0193-6
26	Qi L, Wang Y, Wu E X. D-eigenvalues of diffusion kurtosis tensor. J Comput Appl Math , 2008, 221: 150-157 doi: 10.1016/j.cam.2007.10.012
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. 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 doi: 10.1137/090778766
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 doi: 10.1002/nla.822
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 doi: 10.4208/jcm.1110-m11si09

[1]	Yizheng FAN, Zhu ZHU, Yi WANG. Least H-eigenvalue of adjacency tensor of hypergraphs with cut vertices[J]. Front. Math. China, 2020, 15(3): 451-465.
[2]	Hongmei YAO, Li MA, Chunmeng LIU, Changjiang BU. Brualdi-type inclusion sets of Z-eigenvalues and l^k,s-singular values for tensors[J]. Front. Math. China, 2020, 15(3): 601-612.
[3]	Gang WANG, Yuan ZHANG, YijuWANG WANG. Brauer-type bounds for Hadamard product of nonnegative tensors[J]. Front. Math. China, 2020, 15(3): 555-570.
[4]	Haibin CHEN, Yiju WANG, Guanglu ZHOU. High-order sum-of-squares structured tensors: theory and applications[J]. Front. Math. China, 2020, 15(2): 255-284.
[5]	Xin LI, Jiming GUO, Zhiwen WANG. Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)[J]. Front. Math. China, 2019, 14(6): 1213-1230.
[6]	Kinkar Chandra DAS, Huiqiu LIN, Jiming GUO. Distance signless Laplacian eigenvalues of graphs[J]. Front. Math. China, 2019, 14(4): 693-713.
[7]	Jiahao XU, Xin ZHAO. Absence of eigenvalues for quasiperiodic Schrödinger type operators[J]. Front. Math. China, 2019, 14(3): 645-659.
[8]	Changli LIU, Ren-Cang LI. Structured backward error for palindromic polynomial eigenvalue problems, II: Approximate eigentriplets[J]. Front. Math. China, 2018, 13(6): 1397-1426.
[9]	Yueshuang LI. Approximation theorem for principle eigenvalue of discrete p-Laplacian[J]. Front. Math. China, 2018, 13(5): 1045-1061.
[10]	Haibin CHEN, Liqun QI, Yisheng SONG. Column sufficient tensors and tensor complementarity problems[J]. Front. Math. China, 2018, 13(2): 255-276.
[11]	Yuan HOU, An CHANG, Lei ZHANG. Largest H-eigenvalue of uniform s-hypertrees[J]. Front. Math. China, 2018, 13(2): 301-312.
[12]	Lu YE, Zhongming CHEN. Further results on B-tensors with application to location of real eigenvalues[J]. Front. Math. China, 2017, 12(6): 1375-1392.
[13]	Haibin CHEN, Yiju WANG. On computing minimal H-eigenvalue of sign-structured tensors[J]. Front. Math. China, 2017, 12(6): 1289-1302.
[14]	Changjiang BU,Yamin FAN,Jiang ZHOU. Laplacian and signless Laplacian Z-eigenvalues of uniform hypergraphs[J]. Front. Math. China, 2016, 11(3): 511-520.
[15]	Junjie YUE,Liping ZHANG,Mei LU. Largest adjacency, signless Laplacian, and Laplacian H-eigenvalues of loose paths[J]. Front. Math. China, 2016, 11(3): 623-645.

Viewed

Full text

Abstract

Cited

Shared

Discussed