Sum-of-Squares Decomposition and Augmented Vandermonde Decomposition of Strong Hankel Tensors: Theory and Algorithms

Weiyang Ding, Liqun Qi, Yimin Wei

TL;DR

This paper provides a complete characterization of "strong" Hankel tensors—multi-dimensional arrays whose underlying matrix structure is positive semi-definite. The authors prove these tensors inherit critical properties like being "sum-of-squares" (SOS) and provide concrete, numerically stable algorithms to decompose them into simpler, interpretable components.

What Problem Does This Paper Address?

Hankel matrices are fundamental in signal processing, control theory, and data fitting. However, as we move into the world of "Big Data," we often encounter higher-order versions called Hankel tensors. A major challenge in tensor analysis is determining if a tensor is positive semi-definite (PSD)—meaning it always yields a non-negative value when multiplied by a vector—and whether it can be represented as a sum-of-squares (SOS) of polynomials.

While every SOS tensor is PSD, the reverse is not always true. This paper focuses on a specific, important class called strong Hankel tensors (where the associated Hankel matrix is PSD). The authors aim to bridge the gap between matrix theory and tensor theory by proving that these strong Hankel tensors are always SOS and can be fully described through specific mathematical decompositions.

Methods

The authors utilize a "convolution formula" that links tensor-vector products to discrete convolutions of the tensor's generating vector. Their approach relies on several key techniques:

  • Inheritance Properties: They prove that if a lower-order Hankel tensor (like a matrix) is PSD or SOS, a higher-order version sharing the same generating vector "inherits" these properties.
  • Algorithm 1 (SOS Decomposition): This algorithm uses the Takagi factorization of the associated Hankel matrix to construct a concrete SOS representation for the tensor.
  • Algorithm 2 (Augmented Vandermonde Decomposition): Standard Vandermonde decompositions are often "incomplete" because their mathematical space isn't closed. The authors introduce an "augmented" version that adds a specific rank-one term to ensure every strong Hankel tensor can be perfectly represented.
  • Algorithm 3 (Nonnegative Case): A specialized procedure to handle tensors where all entries are non-negative, ensuring the resulting decomposition also uses non-negative coefficients.

Datasets

The paper does not use real-world datasets but validates its theoretical findings and algorithms through rigorous numerical experiments:

  • Hilbert Tensors: A classic type of Hankel tensor used as a benchmark for positive definiteness.
  • Synthetic Strong Hankel Tensors: The authors tested their algorithms on 10,000 randomly generated 4th-order, 10-dimensional strong Hankel tensors to evaluate numerical stability and precision.
  • Simple Counterexamples: They use specific low-dimensional tensors (e.g., 4th-order 3D) to illustrate why certain standard decompositions fail without the "augmented" term.

Key Insights and Ideas

  • Lifting Properties from 2D to $m$D: The most powerful insight is the "inheritance property." It allows researchers to take well-understood properties of 2D matrices and confidently apply them to complex $m$-dimensional tensors, provided they share a generating vector.
  • Strong implies SOS: In general tensor theory, PSD does not imply SOS. However, this paper proves that for the Hankel structure, being "strong" (having a PSD associated matrix) is a sufficient condition for being SOS.
  • Closing the Cone: The "Augmented" part of the Vandermonde decomposition is a clever fix for a known topological problem. By adding the term $\alpha_r \mathbf{e}_n^{\circ m}$, the authors "close" the set of representable tensors, providing a "full picture" of the strong Hankel tensor space.
  • The Convolution Bridge: By framing tensor-vector multiplication as a discrete convolution, the authors connect structured linear algebra to classical polynomial analysis.

Key Results

  • Theoretical Completeness: The authors successfully proved that every strong Hankel tensor admits both a concrete SOS decomposition and an augmented Vandermonde decomposition with positive coefficients.
  • Numerical Precision: In their large-scale test of 10,000 random tensors, the algorithms recovered the exact decomposition parameters with an average relative error of just $4.79 \times 10^{-12}$, demonstrating extreme accuracy.
  • Hilbert Tensor Validation: The study confirmed that Hilbert tensors are a subset of non-negative strong Hankel tensors and can be efficiently decomposed using the proposed methods.

Limitations and Future Work

  • Focus on "Strong" Tensors: The results are specific to tensors whose associated matrices are PSD. The authors acknowledge that there exist "non-strong" PSD Hankel tensors that do not fall under this umbrella.
  • Open Questions: Identifying the "simplest" non-strong PSD Hankel tensors remains an open challenge.
  • Additional Constraints: The authors suggest that exploring how these properties change under further constraints, such as strict non-negativity of all entries, is a promising direction for future research.

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{ding2016sum,
  author = {Weiyang Ding and Liqun Qi and Yimin Wei},
  title = {{Sum-of-Squares Decomposition and Augmented Vandermonde Decomposition of Strong Hankel Tensors: Theory and Algorithms}},
  booktitle = {BIT},
  year = {2016},
  doi = {10.1007/s10543-016-0622-0},
}
Figure