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

Haibin Chen Qufu Normal University, Rizhao, China Yannan Chen South China normal University, China Guoyin Li University of New South Wales Liqun Qi The Hong Kong Polytechnic University,

Numerical Analysis and Scientific Computing Numerical Linear Algebra Optimization and Control mathscidoc:2108.25005

25, (1), e2125, 2018.11
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 thewell-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 themaximumH-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.
copositivity, eigenvalues, Laplacian tensor, semidefinite program, spectral hypergraph, structured tensors, sum-of-squares polynomials
[ Download ] [ 2021-08-23 15:59:49 uploaded by gyli ] [ 156 downloads ] [ 0 comments ]
@inproceedings{haibin2018a,
  title={A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test},
  author={Haibin Chen, Yannan Chen, Guoyin Li, and Liqun Qi},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20210823155949638583865},
  volume={25},
  number={1},
  pages={e2125},
  year={2018},
}
Haibin Chen, Yannan Chen, Guoyin Li, and Liqun Qi. A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test. 2018. Vol. 25. pp.e2125. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20210823155949638583865.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved