Inheritance properties and sum-of-squares decomposition of Hankel tensors: theory and algorithms

Weiyang Ding, Liqun Qi, Yimin Wei

TL;DR

This paper reveals "inheritance properties" of Hankel tensors, proving that if a lower-order Hankel structure (like a matrix) is positive semi-definite or a Sum-of-Squares (SOS), its higher-order descendants sharing the same "generating vector" will be too. The authors provide the first concrete algorithm to decompose strong Hankel tensors into sums of squares and propose a new conjecture linking odd-order and even-order tensors.

What Problem Does This Paper Address?

In data analysis and signal processing, we often encounter Hankel matrices—square arrays where each ascending skew-diagonal is constant. Their higher-dimensional cousins, Hankel tensors, are increasingly vital for tasks like multidimensional seismic trace interpolation and exponential data fitting.

The big challenge lies in "positivity." Determining if a high-order tensor is positive semi-definite (PSD)—meaning it never yields a negative value when multiplied by vectors—is generally an NP-hard problem. While previous researchers proved that certain "strong" Hankel tensors are always Sum-of-Squares (SOS), they didn't provide a practical way to actually perform that decomposition. This paper seeks to bridge the gap between the well-understood world of Hankel matrices and the complex frontier of higher-order Hankel tensors.

Methods

The authors leverage a powerful mathematical bridge: the Convolution Formula. By treating tensor-vector products as discrete convolutions, they can represent complex tensor operations as simpler polynomial multiplications.

Key technical components include:

  • Augmented Vandermonde Decomposition: They represent Hankel tensors using a sum of rank-one tensors derived from Vandermonde vectors. This allows them to "unfold" the tensor's properties.
  • Takagi Factorization: For the matrix case, they use this specialized singular value decomposition to kickstart the SOS decomposition for the higher-order tensor.
  • Algorithmic Framework: 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.

Datasets

As a theoretical and algorithmic paper, the authors do not use large-scale empirical datasets. Instead, they validate their theory using structured mathematical objects:

  • Hilbert Tensors: A famous class of Hankel tensors known for being strictly positive definite.
  • Synthetic Hankel Tensors: 4th-order tensors generated with specific dimensions (3D and 5D) to test the precision of their decomposition algorithms.
  • Randomized Simulations: They ran 10,000 experiments on randomly generated tensors to demonstrate that their recovery algorithm is numerically stable and highly accurate.

Key Insights and Ideas

  • Properties are "Inherited": The core "aha!" moment is that the "generating vector" acts like DNA. If the vector produces a PSD matrix (order 2), it will also produce a PSD 4th-order, 6th-order, or any $2q$-order tensor.
  • Eigenvalue Bounds: The authors show that the extremal H-eigenvalues (a specific type of tensor eigenvalue) of a high-order tensor are bounded by the eigenvalues of its lower-order ancestors, scaled by specific constants. This makes it possible to estimate the behavior of complex tensors using much simpler matrix math.
  • From Existence to Construction: Previously, we knew strong Hankel tensors could be written as a sum of squares. This paper provides the "how," turning an existential proof into a usable engineering tool.
  • The Odd-Order Bridge: They prove a second inheritance property showing that even odd-order Hankel tensors (which can't be PSD in the traditional sense) still inherit the "non-negativity" of their H-eigenvalues from their associated matrices.

Key Results

  • Mathematical Proofs: The paper successfully proves two major inheritance properties regarding PSD, SOS, and H-eigenvalue characteristics.
  • Decomposition Accuracy: In numerical tests, the proposed algorithm recovered the augmented Vandermonde decomposition of a 10-dimensional tensor with an average relative error of only $4.78 \times 10^{-12}$, demonstrating near-perfect numerical precision.
  • Hilbert Tensor Confirmation: They computationally confirmed that Hilbert tensors are non-negative strong Hankel tensors with non-negative Vandermonde decompositions.

Limitations and Future Work

The primary limitation is the "Third Inheritance Property," which the authors were unable to prove. They have left it 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 be significant because it would create a definitive link between odd-order symmetric tensors and positive semi-definite symmetric tensors, potentially opening new doors in the study of tensor eigenvalues. Additionally, while the eigenvalue bounds are quantified for PSD cases, the authors note it is currently unclear how to quantify these bounds when the associated matrix has a mix of positive and negative eigenvalues.

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},
}

Loading related content...

Figure