弱不可约非负张量 H-谱半径的算法

Algorithm for Computing the H-Spectral Radius of Weakly Irreducible Nonnegative Tensors

摘要

给出非负张量 H-谱半径的一个幂型算法,并利用张量的有向图证明该算法是 R-线性收敛的,进而得到算法线性收敛的一般条件.结果表明,该算法适用于所有弱不可约非负张量 H-谱半径的计算,与 NQZ算法适用于弱本原张量比较适用范围更广.

Abstract

A power-type iterative algorithm is proposed for computing the H-spectral radius of nonnegative tensors. By utilizing the directed graph associated with the tensor, the R-linear convergence of the algorithm is established, and sufficient conditions for linear convergence are further derived. The proposed algorithm is applicable to all weakly irreducible nonnegative tensors. Compared with the NQZ algorithm, which is designed for weakly primitive tensors, the proposed method has a broader range of applicability.

关键词

非负张量 / H-谱半径 / 幂型算法 / R-线性收敛

Key words

nonnegative tensor / H-spectral radius / power-type algorithm / R-linear convergence

参考文献

[1] Arrigo F, Tudisco F. Multi-dimensional, Multilayer, Nonlinear and Dynamic HITS[C]// Proceedings of the 2019 SIAM International Conference on Data Mining. [S. l.]: SIAM, 2019: 369-377.

[2] Benson A R. Three Hypergraph Eigenvector Centralities[J]. SIAM J Math Data Sci, 2019, 1(2): 293-312.

[3] Tudisco F, Arrigo F, Gautier A. Node and Layer Eigenvector Centralities for Multiplex Networks[J]. SIAM J Appl Math, 2018, 78(2): 853-876.

[4] Cichocki A, Zdunek R, Phan A H, et al. Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation[M]. Chichester: John Wiley & Sons, Ltd., 2009.

[5] Chang K C, Pearson K, Zhang T. Perron-Frobenius Theorem for Nonnegative Tensors[J]. Commun Math Sci, 2008, 6(2): 507-520.

[6] Yang Y N, Yang Q Z. Further Results for Perron-Frobenius Theorem for Nonnegative Tensors[J]. SIAM J Matrix Anal Appl, 2010, 31(5): 2517-2530.

[7] Friedland S, Gaubert S, Han L. Perron-Frobenius Theorem for Nonnegative Multilinear Forms and Extensions[J]. Linear Algebra Appl, 2013, 438(2): 738-749.

[8] Gautier A, Tudisco F, Hein M. The Perron-Frobenius Theorem for Multihomogeneous Mappings[J]. SIAM J Matrix Anal Appl, 2019, 40(3): 1179-1205.

[9] Gautier A, Tudisco F, Hein M. Nonlinear Perron-Frobenius Theorems for Nonnegative Tensors[J]. SIAM Rev, 2023, 65(2): 495-536.

[10] Qi L Q, Luo Z Y. Tensor Analysis: Spectral Theory and Special Tensors[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2017.

[11] Qi L Q, Chen H B, Chen Y N. Tensor Eigenvalues and Their Application[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2018.

[12] Liu G M, Lv H B. Bounds for Spectral Radius of Nonnegative Tensors Using Matrix-Digragh-Based Approach[J]. J Ind Manag Optim, 2023, 19(1): 105-116.

[13] 吕洪斌, 林志兴. 一类双对角占优 H-张量及其应用[J]. 东北师大学报(自然科学版), 2024, 56(4):20-25.

[14] (Lü H B, Lin Z X. A Class of Bi-diagonally Dominant H-Tensor and Its Applications[J]. Journal of Northeast University (Naturnal Science Edition), 2024, 56(4): 20-25.)

[15] Hu S L, Huang Z H, Qi L Q. Strictly Nonnegative Tensors and Nonnegative Tensor Partition[J]. Sci China (Math), 2014, 57(1): 181-195.

[16] 林志兴, 吕洪斌. 本质拟对称非负张量 H-谱半径的算法[J]. 吉林大学学报(理学版), 2025, 63(2):411-416.

[17] (Lin Z X, Lü H B. Algorithm for H-Spectral Radius of Essentially Quasi-symmetric Non-negative Tensors[J]. Journal of Jilin University (Science Edition), 2025, 63(2): 411-416.)

[18] Ng M, Qi L Q, Zhou G L. Finding the Largest Eigenvalue of a Nonnegative Tensor[J]. SIAM J Matrix Anal Appl, 2009, 31(3): 1090-1099.

[19] Qi L Q. Eigenvalue of a Real Supersymmetric Tensor[J]. J Symbolic Comput, 2005, 40(6): 1302-1324.

[20] Lim L H. Singular Values and Eigenvalues of Tensors: A Variational Approach[C]// Proceeding of the IEEE International Workshop on Computational Advances in Multi-sensor Adaptive Processing. [S.l.]: IEEE, 2005: 129-132.

[21] Friedland S, Gaubert S, Han L. Perron-Frobenius Theorem for Nonnegative Multilinear Forms and Extensions[J]. Linear Algebra Appl, 2013, 438(2): 738-749.

[22] Lv H B, Chen M X. Linear Convergence of the NQZ Algorithm for Finding the H-Spectral Radius of Nonnegative Tensors[J/OL]. Plos One, (2026-01-23)[2026-03-10]. https://doi.org/10.1371/journal.pone.0338496.

[23] Zhang L P, Qi L Q. Linear Convergence of an Algorithm for Computing the Largest Eigenvalue of a Nonnegative Tensors[J]. Numer Linear Algebra Appl, 2012, 19(5): 830-841.

基金资助

国家自然科学基金(62372256)

福建省自然科学基金(2026J0011063)