Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/75021
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
Eigenvalues
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.
URI: http://hdl.handle.net/10397/75021
ISSN: 1070-5325
EISSN: 1099-1506
DOI: 10.1002/nla.2125
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

2
Last Week
1
Last month
Citations as of Apr 15, 2018

WEB OF SCIENCETM
Citations

2
Last Week
1
Last month
Citations as of Apr 24, 2018

Page view(s)

1
Citations as of Apr 23, 2018

Google ScholarTM

Check

Altmetric


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