Finding the maximum eigenvalue of a class of tensors with applications in copositivity test and hypergraphs

preprint2016arXivOpen access

Abstract

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. This paper is devoted to a semi-definite program algorithm for computing the maximum HH-eigenvalue of a class of tensors with sign structure called WW-tensors. The class of WW-tensors extends the well-studied nonnegative tensors and essentially nonnegative tensors, and covers some important tensors arising naturally from spectral hypergraph theory. Our algorithm is based on a new structured sums-of-squares (SOS) decomposition result for a nonnegative homogeneous polynomial induced by a WW-tensor. This SOS decomposition enables us to show that computing the maximum HH-eigenvalue of an even order symmetric WW-tensor is equivalent to solving a semi-definite program, and hence can be accomplished in polynomial time. Numerical examples are given to illustrate that the proposed algorithm can be used to find maximum HH-eigenvalue of an even order symmetric WW-tensor with dimension up to 10,00010,000. We present two applications for our proposed algorithm: we first provide a polynomial time algorithm for computing the maximum HH-eigenvalues of large size Laplacian tensors of hyper-stars and hyper-trees; second, we show that the proposed SOS algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended ZZ-tensors, whose order may be even or odd. Numerical experiments illustrate that our structured semi-definite program algorithm is effective and promising.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.