Please use this identifier to cite or link to this item:
Title: A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test
Authors: Chen, H
Chen, Y
Li, G
Qi, L 
Keywords: Copositivity
Laplacian tensor
Semidefinite program
Spectral hypergraph
Structured tensors
Sum-of-squares polynomials
Issue Date: 2018
Publisher: John Wiley and Sons Ltd
Source: Numerical linear algebra with applications, 2018, v. 25, no. 1, e2125 How to cite?
Journal: Numerical linear algebra with applications 
Abstract: 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.
ISSN: 1070-5325
EISSN: 1099-1506
DOI: 10.1002/nla.2125
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Oct 4, 2018


Last Week
Last month
Citations as of Oct 12, 2018

Page view(s)

Last Week
Last month
Citations as of Oct 14, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.