American Institute of Mathematical Sciences

Advanced
January  2021, 17(1): 29-50. doi: 10.3934/jimo.2019097

Perron vector analysis for irreducible nonnegative tensors and its applications

Wen Li 1, , Wei-Hui Liu 2,, and  Seak Weng Vong 2,

1. 

School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China
2. 

Department of Mathematics, University of Macau, Macau, China

* Corresponding author: Wei-Hui Liu

Received  January 2019 Revised  March 2019 Published  July 2019

Fund Project: The first author is supported by NSFC grant 11671158, U1811464 and 11771159. The second author is supported by NSFC grant 11571124 and UM grant MYRG2016-00077-FST. The third author is supported by UM grant MYRG2017-00098-FST

In this paper, we analyse the Perron vector of an irreducible nonnegative tensor, and present some lower and upper bounds for the ratio of the smallest and largest entries of a Perron vector based on some new techniques, which always improve the existing ones. Applying these new ratio results, we first refine two-sided bounds for the spectral radius of an irreducible nonnegative tensor. In particular, for the matrix case, the new bounds also improve the corresponding ones. Second, we provide a new Ky Fan type theorem, which improves the existing one. Third, we refine the perturbation bound for the spectral radii of nonnegative tensors, from which one may derive a comparison theorem for spectral radii of nonnegative tensors. Numerical examples are given to show the efficiency of the theoretical results.

Keywords: Nonnegative tensor, Perron vector, irreducibility, spectral radius, bound.
Mathematics Subject Classification: Primary: 15A69.
Citation: Wen Li, Wei-Hui Liu, Seak Weng Vong. Perron vector analysis for irreducible nonnegative tensors and its applications. Journal of Industrial & Management Optimization, 2021, 17 (1) : 29-50. doi: 10.3934/jimo.2019097
References:
[1]

K. Chang, K. Pearson and T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci., 6 (2008), 507-520.  doi: 10.4310/CMS.2008.v6.n2.a12.  Google Scholar

[2]

K. Chang, K. Pearson and T. Zhang, Primitivity, the convergence of the NQZ method, and the largest eigenvalue for nonnegative tensors, SIAM J. Matrix Anal. Appl., 33 (2011), 806-819.  doi: 10.1137/100807120.  Google Scholar

[3]

K. Chang and T. Zhang, On the uniqueness and non-uniqueness of the positive $Z$-eigenvector for transition probability tensors, J. Math. Anal. Appl., 408 (2013), 525-540.  doi: 10.1016/j.jmaa.2013.04.019.  Google Scholar

[4]

L. De Lathauwer, B. De Moor and J. Vandewalle, A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21 (2000), 1253-1278.  doi: 10.1137/S0895479896305696.  Google Scholar

[5]

S. Friedland, S. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl., 438 (2013), 738-749.  doi: 10.1016/j.laa.2011.02.042.  Google Scholar

[6] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, UK, 1991.   Google Scholar
[7]

S. Hu and L. Qi, Algebraic connectivity of an even uniform hypergraph, J. Comb. Optim., 24 (2012), 564-579.  doi: 10.1007/s10878-011-9407-1.  Google Scholar

[8]

W. Li, L. B. Cui and M. Ng, The perturbation bound for the Perron vector of a transition probability tensor, Numer. Linear Algebra Appl., 20 (2013), 985-1000.  doi: 10.1002/nla.1886.  Google Scholar

[9]

W. Li and M. Ng, On the limiting probability distribution of a transition probability tensor, Linear Multilin. Algebra, 62 (2014), 362-385.  doi: 10.1080/03081087.2013.777436.  Google Scholar

[10]

W. Li and M. K. Ng, The perturbation bound for the spectral radius of a nonnegative tensor, Adv. Numer. Anal., 2014 (2014), 10pp. doi: 10.1155/2014/109525.  Google Scholar

[11]

W. Li and M. K. Ng, Some bounds for the spectral radius of nonnegative tensors, Numer. Math., 130 (2015), 315-335.  doi: 10.1007/s00211-014-0666-5.  Google Scholar

[12]

L. H. Lim, Singular values and eigenvalues of tensors: A variational approach, in Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 05, vol. 1, IEEE Computer Society Press, Piscataway, NJ, 2005, 129-132. Google Scholar

[13]

Q. Liu, C. Li and C. Zhang, Some inequalities on the Perron eigenvalue and eigenvectors for positive tensors, J. of Math. Inequal., 10 (2016), 405-414.  doi: 10.7153/jmi-10-31.  Google Scholar

[14]

H. Minc, Nonnegative Matrices, John Wiley & Sons, New York, 1988.  Google Scholar

[15]

M. Ng, L. Qi and G. Zhou, Finding the largest eigenvalue of a non-negative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099.  doi: 10.1137/09074838X.  Google Scholar

[16]

K. Pearson, Essentially positive tensors, Int. J. Algebra, 4 (2010), 421-426.   Google Scholar

[17]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. of Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[18]

L. Qi, Symmetric nonnegative tensor and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015.  Google Scholar

[19]

L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, Society for Industrial and Applied Mathematics, Pennsylvania, 2017. doi: 10.1137/1.9781611974751.ch1.  Google Scholar

[20]

Z. Wang and W. Wu, Bounds for the greatest eigenvalue of positive tensors, J. of Indust. and Mgmt. Optim., 10 (2014), 1031-1039.  doi: 10.3934/jimo.2014.10.1031.  Google Scholar

[21]

Y. N. Yang and Q. Z. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors, SIAM J. Matrix Anal. Appl., 31 (2010), 2517-2530.  doi: 10.1137/090778766.  Google Scholar

[22]

Q. Z. Yang and Y. N. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors Ⅱ, SIAM J. Matrix Anal. Appl., 32 (2011), 1236-1250.  doi: 10.1137/100813671.  Google Scholar

show all references

References:
[1]

K. Chang, K. Pearson and T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci., 6 (2008), 507-520.  doi: 10.4310/CMS.2008.v6.n2.a12.  Google Scholar

[2]

K. Chang, K. Pearson and T. Zhang, Primitivity, the convergence of the NQZ method, and the largest eigenvalue for nonnegative tensors, SIAM J. Matrix Anal. Appl., 33 (2011), 806-819.  doi: 10.1137/100807120.  Google Scholar

[3]

K. Chang and T. Zhang, On the uniqueness and non-uniqueness of the positive $Z$-eigenvector for transition probability tensors, J. Math. Anal. Appl., 408 (2013), 525-540.  doi: 10.1016/j.jmaa.2013.04.019.  Google Scholar

[4]

L. De Lathauwer, B. De Moor and J. Vandewalle, A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21 (2000), 1253-1278.  doi: 10.1137/S0895479896305696.  Google Scholar

[5]

S. Friedland, S. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl., 438 (2013), 738-749.  doi: 10.1016/j.laa.2011.02.042.  Google Scholar

[6] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, UK, 1991.   Google Scholar
[7]

S. Hu and L. Qi, Algebraic connectivity of an even uniform hypergraph, J. Comb. Optim., 24 (2012), 564-579.  doi: 10.1007/s10878-011-9407-1.  Google Scholar

[8]

W. Li, L. B. Cui and M. Ng, The perturbation bound for the Perron vector of a transition probability tensor, Numer. Linear Algebra Appl., 20 (2013), 985-1000.  doi: 10.1002/nla.1886.  Google Scholar

[9]

W. Li and M. Ng, On the limiting probability distribution of a transition probability tensor, Linear Multilin. Algebra, 62 (2014), 362-385.  doi: 10.1080/03081087.2013.777436.  Google Scholar

[10]

W. Li and M. K. Ng, The perturbation bound for the spectral radius of a nonnegative tensor, Adv. Numer. Anal., 2014 (2014), 10pp. doi: 10.1155/2014/109525.  Google Scholar

[11]

W. Li and M. K. Ng, Some bounds for the spectral radius of nonnegative tensors, Numer. Math., 130 (2015), 315-335.  doi: 10.1007/s00211-014-0666-5.  Google Scholar

[12]

L. H. Lim, Singular values and eigenvalues of tensors: A variational approach, in Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 05, vol. 1, IEEE Computer Society Press, Piscataway, NJ, 2005, 129-132. Google Scholar

[13]

Q. Liu, C. Li and C. Zhang, Some inequalities on the Perron eigenvalue and eigenvectors for positive tensors, J. of Math. Inequal., 10 (2016), 405-414.  doi: 10.7153/jmi-10-31.  Google Scholar

[14]

H. Minc, Nonnegative Matrices, John Wiley & Sons, New York, 1988.  Google Scholar

[15]

M. Ng, L. Qi and G. Zhou, Finding the largest eigenvalue of a non-negative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099.  doi: 10.1137/09074838X.  Google Scholar

[16]

K. Pearson, Essentially positive tensors, Int. J. Algebra, 4 (2010), 421-426.   Google Scholar

[17]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. of Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.  Google Scholar

[18]

L. Qi, Symmetric nonnegative tensor and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015.  Google Scholar

[19]

L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, Society for Industrial and Applied Mathematics, Pennsylvania, 2017. doi: 10.1137/1.9781611974751.ch1.  Google Scholar

[20]

Z. Wang and W. Wu, Bounds for the greatest eigenvalue of positive tensors, J. of Indust. and Mgmt. Optim., 10 (2014), 1031-1039.  doi: 10.3934/jimo.2014.10.1031.  Google Scholar

[21]

Y. N. Yang and Q. Z. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors, SIAM J. Matrix Anal. Appl., 31 (2010), 2517-2530.  doi: 10.1137/090778766.  Google Scholar

[22]

Q. Z. Yang and Y. N. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors Ⅱ, SIAM J. Matrix Anal. Appl., 32 (2011), 1236-1250.  doi: 10.1137/100813671.  Google Scholar

Figure 1.  Comparison between two Ky Fan type Theorems
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The results of randomly constructed tensors
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The results of perturbation bounds (left) n = 5 and (right) n = 10
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Comparisons with the upper bounds for the ratio
$ \omega_1 $ in (3) $ \omega_2 $ in (4) $ \omega_3 $ in (5) $ \omega_4 $ in (11)
0.5575 0.5307 0.4855 0.5244
Table Options

Download as excel

$ \omega_1 $ in (3) $ \omega_2 $ in (4) $ \omega_3 $ in (5) $ \omega_4 $ in (11)
0.5575 0.5307 0.4855 0.5244
Table 2.  Comparisons with the lower bounds for ratio
Example 2 Example 3 Example 4
Actual value of $ \frac{x_{\min}}{x_{\max}} $ 0.9873 0.6402 0.6794
$ \kappa_0 $ in (2) 0.6300 0.3969 0.5000
$ \kappa_1 $ in (3) 0.7857 0.2083 0.3077
$ \kappa_2 $ in (4) 0.5848 0.5000 0.4642
$ \kappa_3^{(1)} $ in (13) $ {\bf{0.9662}} $ 0.2808 0.3445
(t = -5.5602) (t = -5.7276) (t = -5.0250)
$ \kappa_3^{(2)} $ in (16) 0.9258 0.5000 $ {\bf{0.5539}} $
(also in (13)) (t = -5.1168) (t = -2.2315) (t = -2.2956)
$ \kappa_3^{(3)} $ in (13) 0.6300 $ {\bf{0.5724}} $ 0.5503
(t = -3.0000) (t = -3.5887) (t = -2.5208)
$ \kappa_3 $ in (13) $ {\bf{0.9662}} $ $ {\bf{0.5724}} $ $ {\bf{0.5539}} $
Table Options

Download as excel

Example 2 Example 3 Example 4
Actual value of $ \frac{x_{\min}}{x_{\max}} $ 0.9873 0.6402 0.6794
$ \kappa_0 $ in (2) 0.6300 0.3969 0.5000
$ \kappa_1 $ in (3) 0.7857 0.2083 0.3077
$ \kappa_2 $ in (4) 0.5848 0.5000 0.4642
$ \kappa_3^{(1)} $ in (13) $ {\bf{0.9662}} $ 0.2808 0.3445
(t = -5.5602) (t = -5.7276) (t = -5.0250)
$ \kappa_3^{(2)} $ in (16) 0.9258 0.5000 $ {\bf{0.5539}} $
(also in (13)) (t = -5.1168) (t = -2.2315) (t = -2.2956)
$ \kappa_3^{(3)} $ in (13) 0.6300 $ {\bf{0.5724}} $ 0.5503
(t = -3.0000) (t = -3.5887) (t = -2.5208)
$ \kappa_3 $ in (13) $ {\bf{0.9662}} $ $ {\bf{0.5724}} $ $ {\bf{0.5539}} $
Table 3.  Comparisons between (20) and (27)
Dimension $ n = 5 $ $ n = 10 $ $ n = 15 $ $ n = 20 $
Lower bound 42.86% 64.02% 75.64% 81.37%
Upper bound 91.76% 94.50% 95.77% 96.83%
Table Options

Download as excel

Dimension $ n = 5 $ $ n = 10 $ $ n = 15 $ $ n = 20 $
Lower bound 42.86% 64.02% 75.64% 81.37%
Upper bound 91.76% 94.50% 95.77% 96.83%
[1]

Meng Ding, Ting-Zhu Huang, Xi-Le Zhao, Michael K. Ng, Tian-Hui Ma. Tensor train rank minimization with nonlocal self-similarity for tensor completion. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021001
[2]

Aisling McGlinchey, Oliver Mason. Observations on the bias of nonnegative mechanisms for differential privacy. Foundations of Data Science, 2020, 2 (4) : 429-442. doi: 10.3934/fods.2020020
[3]

Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054
[4]

Joel Kübler, Tobias Weth. Spectral asymptotics of radial solutions and nonradial bifurcation for the Hénon equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3629-3656. doi: 10.3934/dcds.2020032
[5]

Bopeng Rao, Zhuangyi Liu. A spectral approach to the indirect boundary control of a system of weakly coupled wave equations. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 399-414. doi: 10.3934/dcds.2009.23.399
[6]

Manxue You, Shengjie Li. Perturbation of Image and conjugate duality for vector optimization. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020176
[7]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[8]

Gaojun Luo, Xiwang Cao. Two classes of near-optimal codebooks with respect to the Welch bound. Advances in Mathematics of Communications, 2021, 15 (2) : 279-289. doi: 10.3934/amc.2020066
[9]

Tomáš Oberhuber, Tomáš Dytrych, Kristina D. Launey, Daniel Langr, Jerry P. Draayer. Transformation of a Nucleon-Nucleon potential operator into its SU(3) tensor form using GPUs. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1111-1122. doi: 10.3934/dcdss.2020383
[10]

Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018
[11]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[12]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269
[13]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[14]

Jianfeng Huang, Haihua Liang. Limit cycles of planar system defined by the sum of two quasi-homogeneous vector fields. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 861-873. doi: 10.3934/dcdsb.2020145
[15]

Jingjing Wang, Zaiyun Peng, Zhi Lin, Daqiong Zhou. On the stability of solutions for the generalized vector quasi-equilibrium problems via free-disposal set. Journal of Industrial & Management Optimization, 2021, 17 (2) : 869-887. doi: 10.3934/jimo.2020002

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (143)
  • HTML views (724)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences