PaperlayerView exact revision on arXiv

Source-linked AI summary

Symmetric tensor decomposition

Jerome Brachat, Pierre Comon, Bernard Mourrain, Elias Tsigaridas

arXiv:0901.3706v2cs.SCmath.AG

TL;DR

Symmetric tensor decomposition extends symmetric matrix SVD but remains difficult because common numerical methods may not exploit symmetry or guarantee global convergence. The paper extends Sylvester’s binary-form approach using apolar duality and Hankel operators, yielding an algorithm for arbitrary order and dimension. Under rank conditions, it also addresses computation and essential uniqueness, including beyond strictly sub-generic ranks.

  • Problem

    Symmetric tensor decomposition has unresolved theoretical and algorithmic issues, while widely used numerical methods may not exploit symmetry or guarantee global convergence.

  • Method

    The paper reformulates decomposition through apolar duality, characterizes rank-r solutions with Hankel-operator rank or commutation conditions, and recovers components using linear algebra.

  • Results

    The algorithm decomposes symmetric tensors of arbitrary order and dimension, and under rank conditions provides answers about computation and essential uniqueness beyond strictly sub-generic ranks.

  • Takeaways & Limitations

    The approach provides tools for efficient decomposition, understanding uniqueness conditions, and detecting tensor rank.

  • Takeaways & Limitations

    Common numerical methods face difficulties because the set of symmetric tensors of rank at most r is not closed and its closure has singularities.

Abstract

from arXiv · show

We present an algorithm for decomposing a symmetric tensor, of dimension n and order d as a sum of rank-1 symmetric tensors, extending the algorithm of Sylvester devised in 1886 for binary forms. We recall the correspondence between the decomposition of a homogeneous polynomial in n variables of total degree d as a sum of powers of linear forms (Waring's problem), incidence properties on secant varieties of the Veronese Variety and the representation of linear forms as a linear combination of evaluations at distinct points. Then we reformulate Sylvester's approach from the dual point of view. Exploiting this duality, we propose necessary and sufficient conditions for the existence of such a decomposition of a given rank, using the properties of Hankel (and quasi-Hankel) matrices, derived from multivariate polynomials and normal form computations. This leads to the resolution of polynomial equations of small degree in non-generic cases. We propose a new algorithm for symmetric tensor decomposition, based on this characterization and on linear algebra computations with these Hankel matrices. The impact of this contribution is two-fold. First it permits an efficient computation of the decomposition of any tensor of sub-generic rank, as opposed to widely used iterative algorithms with unproved global convergence (e.g. Alternate Least Squares or gradient descents). Second, it gives tools for understanding uniqueness conditions, and for detecting the rank.

1. Introduction

The paper addresses symmetric tensor decomposition as a higher-order analogue of symmetric matrix SVD, developing a Sylvester-inspired algorithm based on duality and Hankel-operator conditions. It targets arbitrary order and dimension while addressing computational and uniqueness questions.

  • Motivation: Symmetric tensor decomposition extends the rank determination problem of symmetric matrix SVD to higher-order tensors, whose applications include statistics, engineering, chemometrics, psychometrics, and data analysis.Symmetric tensors arise especially as high-order derivatives and cumulant tensors, while tensor methods are used across several application domains.
  • Motivation: Existing numerical methods may fail to exploit symmetry, optimize sequential criteria, lack global-convergence guarantees, or require ranks much smaller than generic.The rank-≤r set for symmetric tensors is not closed and its closure has singularities associated with tensors of rank greater than r.
  • Approach: The proposed algorithm decomposes symmetric tensors of arbitrary order and dimension into sums of rank-one terms by extending Sylvester’s binary-form method.The paper recasts the problem using apolar duality and linear combinations of evaluations at distinct points.
  • Approach: Necessary and sufficient rank-r decomposition conditions are formulated through Hankel-operator rank constraints or commutation properties.In the binary case, ranks of catalecticant matrices suffice; higher dimensions require an extension step and a small-degree polynomial system followed by an eigenvalue problem.
  • Results: The method is not restricted to strictly sub-generic ranks and provides answers about decomposition uniqueness and computation when stated rank conditions hold.In sub-generic cases, the decomposition is essentially unique up to scale and permutation under suitable rank conditions.
  • Binary case: The paper develops Sylvester’s binary algorithm through Hankel matrices, kernel polynomials, distinct roots, and coefficient recovery from a linear system.For a binary form, the Hankel matrix H[r] has dimensions d − r + 1 × r + 1, and kernel polynomials yield the decomposition roots when distinct.

2. Problem formulations

The paper formulates symmetric tensor decomposition through polynomial powers, Veronese secant varieties, and a dual representation using evaluations at points.

  • 2. Problem formulations: The section introduces three formulations of symmetric tensor decomposition used by different mathematical communities.These formulations support the later algorithmic and algebraic developments.
  • 2.1. Polynomial decomposition: A symmetric tensor corresponds to a homogeneous polynomial, whose decomposition seeks the smallest r expressing it as a sum of dth powers of linear forms.The coefficients of the linear forms and the nonzero scalars define the decomposition, while minimal r is the rank.
  • 2.1. Polynomial decomposition: Direct coefficient matching produces an over-constrained polynomial system with r(n + 1) unknown linear-form coefficients and equations homogeneous of degree d.This approach introduces r! redundant solutions from permuting the linear forms and can require solving high-degree polynomials.
  • 2.1. Polynomial decomposition: The paper motivates a more efficient method than direct polynomial solving for the decomposition problem.The later formulations replace the redundant high-degree system with algebraic and linear-algebraic characterizations.
  • 2.2. Veronese and Secant Varieties: The Veronese map sends a projective linear form to its dth power; its image consists of rank-1 symmetric tensors.Linear combinations of r such points define the corresponding secant varieties and rank or border-rank notions.
  • 2.3. Decomposition using duality: Under apolar duality, the polynomial becomes a linear form whose evaluation on a dth power equals polynomial evaluation at the associated point.This recasts decomposition as finding a minimal combination of evaluations at distinct points, with affine decompositions obtained when the first coordinates are nonzero.

3. Hankel operators and quotient algebra

This section develops Hankel operators and quotient algebras as algebraic tools for characterizing decompositions and recovering their points through multiplication operators.

  • Hankel operators: The bilinear form QΛ(a,b)=Λ(ab) and the Hankel operator HΛ encode polynomial multiplication through the linear form Λ.Their matrices contain entries Λ(x^(α+β)) in monomial and dual bases.
  • Quotient algebra: The kernel IΛ of HΛ is an ideal, and the quotient algebra AΛ=R/IΛ has dimension equal to rank(HΛ).A basis of the quotient can be obtained from a suitable invertible restricted Hankel matrix.
  • Quotient algebra: The quotient algebra AΛ is Gorenstein, with its dual identified with the inverse system generated by Λ.This follows from the annihilator relationship between the inverse system and the kernel ideal.
  • Generalized decomposition: Finite-rank Hankel operators yield quotient algebras whose zeros may have multiplicities, represented through inverse systems generated by differential operators.The generalized decomposition length equals the rank of the corresponding Hankel operator.
  • Radical decompositions: A decomposition into evaluations at r distinct points is equivalent to rank(HΛ)=r together with a radical kernel ideal.When the ideal is radical, the inverse-system polynomials have degree zero because each point has multiplicity one.
  • Recovering decomposition points: Multiplication operators recover the decomposition points: their eigenvalues are evaluations at the zeros, and common eigenvectors correspond to point evaluations.For simple roots, one eigenvector computation for a suitable multiplication operator is sufficient.

4. Truncated Hankel operators

The truncated Hankel formulation characterizes finite-rank extensions through connected monomial bases, commuting multiplication matrices, and equivalent rank conditions.

  • 4. Truncated Hankel operators: The decomposition problem becomes finding the smallest r for which an extension Λ has Hankel rank r and a radical kernel ideal.Such an extension yields a sum of r dth powers of linear forms at distinct points.
  • Basis construction: A monomial basis B is required to be connected to 1, meaning every nonconstant basis monomial is obtained by multiplying a lower-degree basis monomial by a variable.This condition supports the construction of multiplication operators from the truncated data.
  • Extension by commutation: Theorem 4.2 states that a rank-r extension exists exactly when the formal multiplication matrices associated with B commute.When they commute, the extension is defined by evaluating polynomials at these operators applied to 1.
  • Extension by commutation: The commuting relations have degree at most 2 in the multiplication-matrix coefficients, with the degree depending on whether variable multiples remain inside B.This gives a low-degree polynomial characterization of the extension property.
  • Rank conditions: An equivalent criterion requires all (r + 1) × (r + 1) minors of a truncated Hankel matrix to vanish for suitable unknown extension entries.The rank formulation also provides uniqueness of the extension under the stated basis conditions.
  • Algorithmic formulation: The resulting quasi-Hankel system combines linear structural constraints with quadratic and cubic relations in the unknown extension parameters and matrix coefficients.The paper explicitly uses these characterizations in its algorithm for minimal tensor decomposition.

5. Symmetric tensor decomposition algorithm

The paper generalizes Sylvester’s binary-form method to symmetric tensors of arbitrary order and dimension. It uses duality, Hankel structures, quotient algebras, and generalized eigenvalue computations to construct decompositions and handle unknown matrix entries.

  • The algorithm generalizes Sylvester’s decomposition method from binary forms to symmetric tensors of arbitrary order and dimension.
  • The polynomial formulation dehomogenizes the input and seeks a sum of powers of linear forms, equivalently representing a dual element through evaluations at distinct points.
  • Given the rank, generalized eigenvectors recover the evaluation points, after which a linear system determines the coefficients of the rank-one terms.
  • The computational pipeline converts the tensor to a homogeneous polynomial, selects a full-rank principal Hankel minor, constructs quotient-algebra multiplication matrices, and solves an eigenvalue problem.
  • Quasi-Hankel or Catalecticant matrices encode polynomial coefficients, but entries above the known degree may require completion using quotient-algebra conditions or moment-matrix extension methods.
  • In the first example, four terms yield a rank-4 decomposition with coefficients ℓ1 = 3, ℓ2 = 15, ℓ3 = 15, and ℓ4 = 5.
  • A second example has dimension 3, order 4, and rank 6, illustrating continuation of the algorithm after completing previously unknown matrix entries.

6. Conclusions and future work

The paper presents a symmetric tensor decomposition algorithm built from duality, Hankel operators, Gorenstein algebra, truncated Hankel completion, and generalized eigenvalue methods. It leaves complexity and incomplete-tensor decomposition as open questions.

  • The proposed algorithm combines dual reformulation, multivariate Hankel operators, Gorenstein algebra, truncated Hankel completion, and generalized eigenvalue computation.
  • The paper identifies arithmetic and Boolean complexity, and decomposition when not all tensor elements are known, as open questions.

Appendix A. Ternary cubics

The appendix applies the decomposition algorithm to classify ternary cubics by rank and projective orbit. It distinguishes ranks one through five using canonical forms and, for rank three, a square-freeness test.

  • The classification procedure decomposes a ternary cubic into powers of linear forms and then distinguishes cases by the resulting rank.
  • Rank one corresponds to a third power of a linear form and is equivalent to x0^3.
  • Rank two is equivalent to x0^3 + x1^3 and lies in the orbit of x0x1(x0 + x1).
  • Rank three has two possible orbits, distinguished by checking whether the polynomial is square-free through a polynomial–derivative gcd test.
  • Rank four is identified as the generic case, while rank five is maximal and belongs to the orbit of x0^2x1 + x0x2^2.
  • The maximal-rank decomposition includes conjugate complex cubic terms with coefficients −0.97396 − 0.94535 i and −0.97396 + 0.94535 i.

Appendix B. An example of extreme rank

The extreme-rank example constructs quotient-algebra matrices from Hankel data and imposes commutation equations to determine unknown entries. Because the resulting system is not zero-dimensional, five unknowns are selected randomly before completing the decomposition.

  • The example studies a ternary cubic of maximal rank five and forms its quotient-algebra matrix from Hankel-type entries.
  • The resulting maximal-rank decomposition contains a conjugate pair of complex terms with coefficients −0.09056 − 0.0879 i and −0.09056 + 0.0879 i.
  • The matrix equation 0 ∆1∆−1 0 = O produces a system of eight equations in eight unknown Hankel entries.
  • Because the system is not zero-dimensional, the procedure randomly fixes five unknowns before continuing with the decomposition.
Loading 0901.3706v2…