Positive semi-definiteness and sum-of-squares property of hankel tensors and circulant tensors

Abstract

Problems in many applications, such as physics, computing sciences, economic and engineering, can be formulated as tensor problems that usually have special structures. In recently years, there are some classes structured tensors including Toeplitz tensors, Hankel tensors, Hilbert tensors, Vandermonde tensors, Cauchy tensors, M-tensors, P-tensors and others have been generalized from matrices and studied. Hankel tensors and Toeplitz tensors arise from signal processing and some other applications. The positive semi-definiteness of Hankel tensors is a condition that guarantee the existence of solution for a multidimensional moment problem. To identify a general tensor is positive semi-definite (PSD) or not is NP-hard but it is easier to check for structured tensors. The aim of this work is to identify the positive semi-definiteness of Hankel tensors and circulant tensors. A symmetric tensor is uniquely corresponding to a homogeneous polynomial. SOS (sum-of-squares) tensors are connected with SOS polynomials, which is easily to check by solving a semi-definite linear programming problem. SOS tensors are PSD tensors, but not vice versa. Based on these facts, we study the existence problem of PSD non SOS Hankel tensor in the following cases: sixth order three dimensional Hankel tensors, fourth order four dimensional Hankel tensors and generalized anti-circulant tensors. There are no PSD non SOS Hankel tensors to be found in these cases. We also study the three dimensional strongly symmetric circulant tensors, which are special Toeplitz tensors. We give a sufficient and necessary condition for an even order three dimensional strongly symmetric circulant tensors to be positive semi-definite in some cases. For a given even order symmetric tensor, it is positive semi-definite (positive definite) if and only if all of its H-or Z-eigenvalues are nonnegative (positive). In other words, it is positive semi-definite if and only if the smallest H-or Z-eigenvalue is nonnegative. We propose an algorithm to compute extreme eigenvalues of large scale Hankel tensors, which can be used to not only identify positive semi-definiteness but also solve many problems in other applications, such as automatic control, medical imaging, quantum information, and spectral graph theory. Numerical examples show the efficiency of the proposed method.