SOS-Hankel Tensors: Theory and Application

Abstract

Hankel tensors arise from signal processing and some other applications. SOS (sum-of-squares) tensors are positive semi-definite symmetric tensors, but not vice versa. The problem for determining an even order symmetric tensor is an SOS tensor or not is equivalent to solving a semi-infinite linear programming problem, which can be done in polynomial time. On the other hand, the problem for determining an even order symmetric tensor is positive semi-definite or not is NP-hard. In this paper, we study SOS-Hankel tensors. Currently, there are two known positive semi-definite Hankel tensor classes: even order complete Hankel tensors and even order strong Hankel tensors. We show complete Hankel tensors are strong Hankel tensors, and even order strong Hankel tensors are SOS-Hankel tensors. We give several examples of positive semi-definite Hankel tensors, which are not strong Hankel tensors. However, all of them are still SOS-Hankel tensors. Does there exist a positive semi-definite non-SOS-Hankel tensor? The answer to this question remains open. If the answer to this question is no, then the problem for determining an even order Hankel tensor is positive semi-definite or not is solvable in polynomial-time. An application of SOS-Hankel tensors to the positive semi-definite tensor completion problem is discussed. We present an ADMM algorithm for solving this problem. Some preliminary numerical results on this algorithm are reported.

References in corpus (1)

• Double B-tensor and quasi-double B-tensor

Cited by in corpus (6)

• Doubly Nonnegative Tensors, Completely Positive Tensors and Applications
• Positive Semi-Definiteness and Sum-of-Squares Property of Fourth Order Four Dimensional Hankel Tensors
• Further Results on Cauchy Tensors and Hankel Tensors
• Positive Semi-Definiteness of Generalized Anti-Circulant Tensors
• The positive semi-definite cone and sum-of-squares cone of Hankel form
• Three Dimensional Strongly Symmetric Circulant Tensors