A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test

作     者：Chen, Haibin Chen, Yannan Li, Guoyin Qi, Liqun 

作者机构：Qufu Normal Univ Sch Management Sci Rizhao Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou Henan Peoples R China Univ New South Wales Dept Appl Math Sydney NSW Australia Hong Kong Polytech Univ Dept Appl Math Kowloon Hong Kong Peoples R China 

出 版 物：《NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS》 (数值线性代数及其应用)

年 卷 期：2018年第25卷第1期

页      面：n/a-1页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：National Natural Science Foundation of China [11601261, 11401539, 11771405] Natural Science Foundation of Shandong Province [ZR2016AQ12] Development Foundation for Excellent Youth Scholars of Zhengzhou University Australian Research Council Future Fellowship [FT130100038] Hong Kong Research Grant Council [PolyU 501212, 501913, 15302114, 15300715] Australian Research Council [FT130100038] Funding Source: Australian Research Council 

主　　题：copositivity eigenvalues Laplacian tensor semidefinite program spectral hypergraph structured tensors sum-of-squares polynomials 

摘      要：Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W-tensors, which not only extends the well-studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H-eigenvalue of an even-order symmetric W-tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H-eigenvalue of W-tensors and is based on a new structured sums-of-squares decomposition result for a nonnegative polynomial induced by W-tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H-eigenvalue of W-tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H-eigenvalues of large-size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state-of-the-art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z-tensors, whose order may be even or odd.