Eigenvectors of tensors and algorithms for Waring decomposition

Luke Oeding; Giorgio Ottaviani

Source-linked AI summary

Eigenvectors of tensors and algorithms for Waring decomposition

Luke Oeding, Giorgio Ottaviani

arXiv:1103.0203v2Mar 1, 2011math.AG

TL;DR

The paper addresses how to find a polynomial's minimal expression as powers of linear forms, motivated by the need for efficient and reliable tensor-decomposition algorithms. It develops an algebraic-geometric approach using the Sylvester algorithm and tensor eigenvectors. The paper gives an efficient algorithm with rank- and generality-dependent success conditions, alongside bounds on its applicability.

Problem
The paper asks how to compute a polynomial's minimal decomposition into powers of linear forms, amid a stated need for efficient and reliable tensor-decomposition algorithms.
Source: §1 · pp. 1, 4
Method
The paper uses algebraic geometry, the Sylvester algorithm, and tensor eigenvectors to construct an efficient algorithm for symmetric-tensor Waring decomposition.
Source: §1 · p. 3
Results
The algorithm has success conditions tied to sufficiently small rank and generality, and the paper gives bounds and sufficient conditions for its applicability.
Source: §1 · p. 4
Takeaways & Limitations
The approach yields a constructive route to Waring decomposition and also gives a Chern-class proof of the Cartwright-Sturmfels eigenvector count that generalizes to other types of generalized eigenvectors.
Source: §1 · pp. 3–4
The algorithm is not guaranteed to succeed unless the tensor is general and its rank is sufficiently small.
Source: §4.3 · p. 21

Abstract

from arXiv · show

A Waring decomposition of a (homogeneous) polynomial f is a minimal sum of powers of linear forms expressing f. Under certain conditions, such a decomposition is unique. We discuss some algorithms to compute the Waring decomposition, which are linked to the equation of certain secant varieties and to eigenvectors of tensors. In particular we explicitly decompose a general cubic polynomial in three variables as the sum of five cubes (Sylvester Pentahedral Theorem).

1. Introduction

The paper develops an algebraic-geometric algorithm for Waring decomposition using the Sylvester algorithm and tensor eigenvectors. Its success is bounded by rank and generality conditions, with further results on eigenvector counts and decomposition limits.

1. Introduction

For a tensor of rank r, the associated map Pf has rank at most 2r and also supports an efficient decomposition method.For a rank-1 input, Pf has rank 2.Source: §1 · p. 2
For a general tensor in Hom(S2C3, C3), seven eigenvectors are shared by general elements of ker Pf and appear in the unique decomposition of a general plane quintic.This supplies a tensor-eigenvector route to the seven fifth powers in the quintic example; the paper identifies it as novel relative to [LO11].Source: §1 · p. 3
The paper's main contribution is an efficient algorithm for symmetric-tensor Waring decomposition, built from algebraic geometry, the Sylvester algorithm, and tensor eigenvectors.The algorithm follows from geometric results in Proposition 4.1 and Theorem 4.7.Source: §1 · p. 3
The algorithm is not guaranteed to succeed for every tensor: success requires sufficiently low rank and generality, and the paper gives rank bounds and sufficient conditions.It improves the Iarrobino-Kanev bound for catalecticant decomposition and gives sufficient conditions for tensors on three or more variables.Source: §1 · pp. 3–4
At least one failure case reveals a new expression for a rational quartic curve through seven given general points.The paper describes this as a side effect of the algorithm's failure to decompose that tensor.Source: §1 · p. 4
The paper also gives a Chern-class proof of the Cartwright-Sturmfels eigenvector count and generalizes it to other types of generalized eigenvectors.The paper calls these generalized eigenvectors simply eigenvectors of tensors.Source: §1 · p. 4
The paper uses algebraic geometry to pursue efficient and robust tensor-decomposition algorithms, alongside or in combination with existing approaches.The motivation reflects the broad use of tensors across scientific fields and the stated need for efficient, reliable decomposition algorithms.Source: §1 · p. 4

2. Classical methods for tensor decomposition: Sylvester’s catalecticant method

This section reviews generic rank and uniqueness results, then presents the catalecticant algorithm and its success boundaries. The method extracts candidate decomposition points from a kernel, but its reach is limited by catalecticant rank bounds.

2.1. General results on the symmetric rank.

The Alexander-Hirschowitz theorem gives generic ranks, with stated exceptions at d=2, 2≤n≤4 with d=4, and (n,d)=(4,3).Source: §2.1 · p. 5
The construction treats three general-rank uniqueness cases uniformly: binary forms of odd degree, S5C3, and S3C4.Source: §2.1 · p. 6
Brute-force decomposition is time- and memory-consuming and often fails even in small dimensions, motivating more efficient and reliable algorithms.Source: §2.1 · pp. 6–7

2.2. The catalecticant method.

The catalecticant algorithm builds a square catalecticant, computes its kernel and zero set, then solves for coefficients when that set is finite and reduced.Otherwise the algorithm stops and fails.Source: §2.2 · p. 7
The paper gives a sufficient condition for catalecticant success and describes it as improving the Iarrobino-Kanev bound, at least for n≥3.Source: §2.2 · p. 8

2.3. Limits of the catalecticant method.

For v3(P2), the Aronhold equation is not a minor of any catalecticant; failure of the method indicates rank beyond its stated bounds, motivating algorithms that reach larger ranks.Source: §2.3 · p. 9

3. New methods for tensor decomposition: Koszul flattening and eigenvectors of tensors

The section develops Koszul flattenings and tensor eigenvectors into methods for Waring decomposition, including conditions for recovery and a constructive proof of the Sylvester pentahedral theorem. It also interprets eigenvectors geometrically as zero loci of sections of twists of the quotient bundle.

3. New methods for tensor decomposition: Koszul flattening and eigenvectors of tensors

Koszul flattening translates eigenvector tests into kernel conditions: v is an eigenvector of M iff M∈ker(P_vd), and eigenvectors of M imply M∈ker Pf.Source: §3 · p. 11
Theorem 3.4 extends the Cartwright–Sturmfels eigenvector count from a=1 to arbitrary a, with the count depending on a and n.Source: §3 · p. 12
For a=1, Algorithm 3 constructs Pf, finds common projective eigenvectors of its kernel, then solves for coefficients; it stops if the candidate locus is not finite and reduced.Source: §3 · p. 12
For n=2 and odd d=2m+1, 2r ≤ m^2+3m+4 gives Z'=Z, while 2r ≤ m^2+4m+2 still permits Algorithm 3 to recover the unique minimal decomposition.In the second range, Z may be a proper subset of Z'.Source: §3 · p. 13

3.1. The quotient bundle and eigenvectors of tensors.

A tensor M corresponds to a section of a twist of the quotient bundle, and the section’s zero locus consists exactly of M’s eigenvectors.The section is denoted sM and lies in H0(Λ^aQ(m)).Source: §3.1 · p. 14

3.2. Pentahedral example.

For a general cubic f in S^3C^4, the pentahedral theorem gives a unique decomposition into five powers, and the method explicitly finds the five corresponding planes.A general element of the flattening kernel has exactly five eigenvectors; minors are used to compute them.Source: §3.2 · pp. 15–16
In the pentahedral example, the five-point ideal is found symbolically, while numerical methods are used only to compute the individual points.The comparison is with the method of.Source: §3.2 · p. 16

4. New methods for tensor decomposition: bundle method

The bundle method turns tensor decomposition into computing a kernel and its base locus, with conditions under which the decomposition points can be recovered. The section gives a general algorithm, identifies its failure cases, and revisits the quintic and pentahedral examples.

4.1. The bundle construction.

In the bundle construction, the decomposition can be recovered from the base locus of ker Af when the stated surjectivity and base-locus conditions hold.The kernel equals H0(IZ ⊗ E) under the surjectivity condition; an explicit matrix construction makes it accessible by linear algebra.Source: §4.1 · p. 17
The bundle method succeeds on the pentahedral example in under one second, while the brute-force method quickly runs out of memory and time.Source: §4.1 · p. 17

4.2. A side remark on presentations.

A bundle presentation yields an explicit matrix Pf with rank Af and the same kernel base locus, connecting the geometric method to computable polynomials.Source: §4.2 · p. 18

4.3. Vector bundles, statement and proofs of the main results.

The algorithm cannot determine a decomposition when the kernel base locus is infinite or nonreduced; a trivial kernel indicates the input rank exceeds the method's range.The authors state that failure from a trivial kernel provides a lower bound for the input rank.Source: §4.3 · pp. 21–22
When rank(f) = rank(Af) and the kernel base locus has finite length, Algorithm 4 produces all minimal Waring decompositions of f.If the resulting linear system has a unique solution, it gives the unique minimal decomposition.Source: §4.3 · pp. 20–21

4.4. Quintic and Pentahedral examples revisited.

The quintic and pentahedral constructions use general sections vanishing on seven and five points, respectively.Source: §4.4 · p. 22
The method recovers the already classically known cases of unique decomposition for general symmetric tensors, but supplies no additional uniqueness cases.The authors present this as evidence that other such cases may not exist.Source: §4.4 · p. 22

5. Rank bounds for feasibility of our algorithms

The section develops bounds on when the algorithms recover Waring decompositions, using quotient-bundle sections and their base loci. It extends the analysis from P2 to P3 and applies common eigenvectors of Koszul flattenings to recover unique decompositions in stated rank regimes.

Theorem 5.1

For m ≥ 0, h0(Q ⊗ I_Z(m)) = (m + 3)(m + 1) − 2s; equivalently, the map H0(Q(m)) → H0(Q_Z(m)) is surjective.Source: §5 · p. 22
For m ≥ 2, the stated rank bound ensures the base locus of H0(Q ⊗ I_Z(m)) is Z itself; for m = 1, the corresponding bound is s ≤ 3.This is the base-locus criterion used to identify points from sections vanishing on Z.Source: §5 · p. 23

Remark 5.2

When m is even and 2s = m^2 + 4m + 2, H0(Q ⊗ I_Z(m)) is generated by one section, with 1 + m + m^2 base-locus points.The point count is given by c2(Q(m)).Source: §5 · p. 24

Theorem 5.4

For general forms of odd degree d = 2m + 1, Theorem 5.4 identifies rank regimes where common eigenvectors recover the decomposition points and Algorithm 5 yields the unique Waring decomposition.The theorem also gives a modified procedure for odd n and a separate n = 3 case with a = 2.Source: §5 · p. 27

Remark 5.5

For seven general points Z in P4, the locus of common eigenvectors of ker Pf is the unique rational quartic curve passing through Z.The paper presents this as a byproduct of Algorithm 5.Source: §5 · p. 28

6. Using Chern classes to count the number of eigenvectors of a general tensor

This section counts eigenvectors of general tensors through top Chern classes of associated quotient bundles. It applies the principle that a section's zero locus has class equal to the top Chern class when its codimension equals the bundle rank.

Counting via Chern classes

If a rank-r bundle section vanishes on a locus of codimension r, that locus has class equal to the bundle's top Chern class.The section applies this principle to count tensor eigenvectors.Source: §6 · p. 28

Proposition 6.1

The section identifies Proposition 6.1 as a particular case of Cartwright and Sturmfels' more general toric result, which proved a conjecture from.The cited earlier result covered Proposition 6.1 when m is odd.Source: §6 · p. 28
For general M ∈ Hom(S^m V, V), the number of eigenvectors counted with multiplicity equals c_n(Q(m)).The proof identifies the count with this Chern class and computes it using the quotient-bundle formula.Source: §6 · pp. 28–29

Proposition 6.2

For general M ∈ Hom(S^m V, ∧^(n−1)V), the eigenvector count is expressed as c_n(Q*(m + 1)).The proof uses c_i(Q*) = (−1)^i to compute the count.Source: §6 · p. 29

7. Macaulay 2 Implementation

The implementation section describes Macaulay2 workflows for the catalecticant and Koszul flattening algorithms. It reports successful tests over rational and prime-characteristic fields, while noting computational and rationality constraints in some Koszul cases.

7. Macaulay 2 Implementation

The authors implemented the algorithms in Macaulay2, noting that the procedures can be adapted to other computational algebra or linear algebra packages.Their code is available with the arXiv ancillary materials or from the authors.Source: §7 · p. 29

7.1. The catalecticant algorithm implementation.

For relatively small d and n, the catalecticant method quickly computes decompositions within the Theorem 2.4 range and sometimes succeeds at slightly higher ranks for low degree.The tests used prime-characteristic fields or the rationals.Source: §7.1 · pp. 29–30
The catalecticant workflow computes the kernel base locus, obtains apolar forms, solves for coefficients by setting derivatives to zero, and checks the resulting decomposition.Tests succeeded across listed n, d, and s cases; for example, n = 3, d = 6, s ≤ 16.Source: §7.1 · pp. 30–31

7.2. The Koszul flattening algorithm implementation.

The Koszul workflow forms a flattening from catalecticants of first derivatives, then uses minors of kernel maps to find common generalized eigenvectors.The resulting linear forms are polar forms of those used in the decomposition.Source: §7.2 · pp. 31–32
The Koszul tests were sharp over prime-characteristic fields except n = 4, d = 5, where computation slowed as s grew; n = 3, d = 5, s = 8 had rationality problems.The authors suggest numerical eigenvector methods and irrational or complex solutions as possible future adaptations, not tested results.Source: §7.2 · p. 32