Inheritance Properties and Sum-of-Squares Decomposition of Hankel Tensors: Theory and Algorithms

Weiyang Ding, Liqun Qi, Yimin Wei

Abstract

In this paper, we show that if a lower-order Hankel tensor is positive semi-definite (PSD), positive definite, negative semi-definite, negative definite, or a Sum-of-Squares (SOS), then its associated higher-order Hankel tensor with the same generating vector—where the higher order is a multiple of the lower order—inherits these same properties. Furthermore, the extremal H-eigenvalues of the higher-order tensor are bounded by the extremal H-eigenvalues of the lower-order tensor, multiplied by specific constants. Based on this inheritance property, we provide a concrete SOS decomposition for each strong Hankel tensor. We also prove a second inheritance property: a Hankel tensor has no negative (or non-positive, or positive, or non-negative) H-eigenvalues if its associated Hankel matrix shares those traits. Finally, a third inheritance property is proposed as a conjecture.

Introduction

Hankel tensors are multidimensional arrays where each entry depends only on the sum of its indices. These structures are increasingly vital in fields such as signal processing, multidimensional seismic trace interpolation, and exponential data fitting. A central challenge in tensor analysis is determining "positivity"—specifically, whether a tensor is positive semi-definite (PSD). For higher-order tensors, this determination is generally an NP-hard problem. This research addresses this complexity by establishing "inheritance properties" that link the well-understood behavior of Hankel matrices to their higher-order tensor descendants.

The Inheritance of Mathematical Properties

The core insight of this work is that the "generating vector" of a Hankel tensor acts as its mathematical DNA. The authors prove that if a lower-order structure (like a matrix) is PSD or SOS, any higher-order tensor sharing that same generating vector (provided the order is a multiple of the lower order) will also be PSD or SOS.

This inheritance extends to spectral analysis. The authors demonstrate that the extremal H-eigenvalues of a high-order tensor are bounded by the eigenvalues of its lower-order ancestors, scaled by specific constants. This allows researchers to estimate the behavior of complex, high-dimensional tensors using much simpler matrix mathematics.

Constructive Sum-of-Squares (SOS) Decomposition

While previous theoretical work suggested that certain "strong" Hankel tensors are SOS, there was no practical algorithm to perform this decomposition. This paper bridges the gap between existence proofs and engineering tools by introducing a constructive algorithmic framework.

Key Methodologies

  • Convolution Formula: By treating tensor-vector products as discrete convolutions, the authors represent complex tensor operations as simpler polynomial multiplications.
  • Augmented Vandermonde Decomposition: This technique represents Hankel tensors as a sum of rank-one tensors derived from Vandermonde vectors, allowing the "unfolding" of the tensor's properties.
  • Takagi Factorization: For the matrix case, this specialized singular value decomposition is used to initiate the SOS decomposition for higher-order tensors.

Algorithmic Framework and Validation

The paper introduces two primary algorithms. Algorithm 1 provides a constructive method for SOS decomposition, while Algorithm 2 computes the augmented Vandermonde decomposition even when the associated Hankel matrix is rank-deficient.

To validate these algorithms, the authors utilized structured mathematical objects rather than empirical datasets:

  • Hilbert Tensors: A class of Hankel tensors known for being strictly positive definite.
  • Synthetic Simulations: The authors conducted 10,000 experiments on randomly generated 4th-order tensors (3D and 5D). The results demonstrated remarkable numerical stability, with a recovery relative error of only $4.78 \times 10^{-12}$.

The Second Inheritance Property and Future Work

The research further establishes a second inheritance property: even odd-order Hankel tensors (which cannot be PSD in the traditional sense) inherit the sign characteristics of their H-eigenvalues from their associated Hankel matrices.

Despite these breakthroughs, a "Third Inheritance Property" remains unproven. The authors have proposed this as a conjecture: If a lower-order Hankel tensor has no negative H-eigenvalues, does its higher-order multiple necessarily share this trait? Proving this would create a definitive link between odd-order symmetric tensors and PSD symmetric tensors, potentially opening new avenues in the study of tensor eigenvalues and their applications in data science.

Summary updated

Abstract

In this paper, we show that if a lower-order Hankel tensor is positive semi-definite (or positive definite, or negative semi-definite, or negative definite, or SOS), then its associated higher-order Hankel tensor with the same generating vector, where the higher order is a multiple of the lower order, is also positive semi-definite (or positive definite, or negative semi-definite, or negative definite, or SOS, respectively). Furthermore, in this case, the extremal H-eigenvalues of the higher order tensor are bounded by the extremal H-eigenvalues of the lower order tensor, multiplied with some constants. Based on this inheritance property, we give a concrete sum-of-squares decomposition for each strong Hankel tensor. Then we prove the second inheritance property of Hankel tensors, i.e., a Hankel tensor has no negative (or non-positive, or positive, or nonnegative) H-eigenvalues if the associated Hankel matrix of that Hankel tensor has no negative (or non-positive, or positive, or nonnegative, respectively) eigenvalues. In this case, the extremal H-eigenvalues of the Hankel tensor are also bounded by the extremal eigenvalues of the associated Hankel matrix, multiplied with some constants. The third inheritance property of Hankel tensors is raised as a conjecture.
BibTeX
@inproceedings{ding2016inheritance,
  author = {Weiyang Ding and Liqun Qi and Yimin Wei},
  title = {{Inheritance Properties and Sum-of-Squares Decomposition of Hankel Tensors: Theory and Algorithms}},
  booktitle = {BIT},
  year = {2016},
  doi = {10.1007/s10543-016-0622-0},
}
Figure