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, Yannan Chen, Guoyin Li, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

36 Citations (Scopus)

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.
Original languageEnglish
Article numbere2125
JournalNumerical Linear Algebra with Applications
Volume25
Issue number1
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • copositivity
  • eigenvalues
  • Laplacian tensor
  • semidefinite program
  • spectral hypergraph
  • structured tensors
  • sum-of-squares polynomials

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics

Cite this