Eigenvectors of tensors and algorithms for Waring decomposition

Basic Information

• Paper ID: 1103.0203
• Title: Eigenvectors of tensors and algorithms for Waring decomposition
• Authors: Luke Oeding, Giorgio Ottaviani
• Classification: math.AG (Algebraic Geometry)
• Publication Date: November 6, 2012 (arXiv v2)
• Paper Link: https://arxiv.org/abs/1103.0203

Abstract

This paper investigates the Waring decomposition of homogeneous polynomials f, which expresses f as a minimal sum of powers of linear forms. Under specific conditions, such decomposition is unique. The paper discusses algorithms for computing Waring decompositions, which are associated with equations of specific secant varieties and eigenvectors of tensors. In particular, the paper explicitly decomposes a general ternary cubic polynomial as a sum of five cubes (Sylvester's pentahedron theorem).

Research Background and Motivation

Core Problem

The fundamental problem addressed in this paper is: given a polynomial, how can one find its minimal decomposition as a sum of powers of linear forms? This is mathematically termed the Waring decomposition problem.

Significance

1. Theoretical Importance: Waring decomposition is a classical problem in algebraic geometry, closely related to symmetric tensor decomposition
2. Practical Applications: Tensor decomposition is widely applied in algebraic statistics, chemistry, computer science, electrical engineering, neuroscience, physics, and psychometrics
3. Computational Demand: The common theme of the 2010 Monopoli (Italy) conference on tensor decomposition and applications was the need for efficient and reliable tensor decomposition algorithms

Limitations of Existing Methods

1. Catalecticant Matrix Method: Completely successful for binary forms, but only partially successful for n ≥ 2
2. Brute Force Methods: Consume enormous time and memory, frequently fail
3. Numerical Methods: Most tensor problems are extremely difficult and typically intractable

Research Motivation

The paper aims to develop new efficient and robust tensor decomposition algorithms using algebraic geometry as the algorithmic foundation, combined with vector bundle techniques and the concept of tensor eigenvectors.

Core Contributions

1. New Algorithmic Framework: Proposes a novel algorithm (Algorithm 4) based on Koszul flattening and tensor eigenvectors, which is the main contribution of the paper
2. Theoretical Refinement: Improves upon Iarrobino-Kanev's results regarding the applicability boundaries of the catalecticant matrix method (Theorem 2.4)
3. Resolution of Classical Problems: Provides a constructive proof and algorithmic implementation of Sylvester's pentahedron theorem
4. Success Conditions: Establishes sufficient conditions for algorithm success (Theorems 3.5 and 5.4)
5. Geometric Interpretation: Provides a new geometric proof of Cartwright-Sturmfels' results on the number of generalized eigenvectors
6. Implementation Code: Provides Macaulay2 implementation as a starting point for further research

Methodology Details

Problem Formulation

Given a symmetric tensor f ∈ S^d V (equivalent to a homogeneous polynomial of degree d), find its Waring decomposition: $f = \sum_{i=1}^r c_i (v_i)^d$ where v_i ∈ V are linear forms, c_i ∈ ℂ are coefficients, and r is the minimal number for which such decomposition exists (called the symmetric rank).

Core Technique: Koszul Flattening

Construction Method

For f ∈ S^d V, fix 0 ≤ a ≤ n, 1 ≤ m ≤ d-1, and construct a linear map: $P_f : \text{Hom}(S^m V, \wedge^a V) \to \text{Hom}(\wedge^{n-a} V, S^{d-m-1} V)$

When f = v^d, it is defined as: $P_{v^d}(M)(w) = (M(v^m) \wedge v \wedge w)(v^{d-m-1})$

Key Lemma

Lemma 3.3: A vector v ∈ V is an eigenvector of tensor M if and only if M ∈ ker(P_{v^d}).

Tensor Eigenvectors

Definition 3.2: Given M ∈ Hom(S^m V, ∧^a V), a vector v ∈ V is called an eigenvector of tensor M if: $M(v^m) \wedge v = 0$

Vector Bundle Method

The paper uses vector bundles E on algebraic varieties X, constructing linear maps depending on f ∈ W: $A_f : H^0(E) \to H^0(E^* \otimes L)^*$

Proposition 4.1: If f = ∑v_i, Z = {v_1,...,v_r}, then:

• H^0(I_Z ⊗ E) ⊆ ker A_f
• Equality holds when H^0(E^* ⊗ L) → H^0(E^* ⊗ L|_Z) is surjective

General Algorithmic Framework

Algorithm 4 (General Tensor Decomposition Algorithm):

1. Construct the map A_f
2. Compute ker A_f
3. Find the base locus Z' of ker A_f
4. Solve the linear system f = ∑c_i v_i^d

Specific Algorithm Instances

Quintic Curve Decomposition (Algorithm 1)

For f ∈ S^5 ℂ^3:

1. Construct an 18×18 block matrix P_f
2. Compute ker P_f, select a general element M
3. Find 7 eigenvectors through the zero set of 2×2 minors
4. Solve the linear system to obtain the unique decomposition

Pentahedron Theorem (Algorithm 3)

For f ∈ S^3 ℂ^4:

1. Set a=2, m=1 to construct P_f
2. Compute the 9-dimensional kernel space
3. Find 5 eigenvectors (corresponding to the 5 planes of the pentahedron)
4. Obtain the unique decomposition

Theoretical Results

Success Boundaries

Theorem 2.4: Improved boundary for the catalecticant matrix method

• Even degree: r ≤ (n+m choose n) - n - 1
• Odd degree: r ≤ (n+m-1 choose n)

Theorem 3.5: Boundary for the Koszul method in the n=2 case

• If 2r ≤ m² + 3m + 4, the algorithm succeeds
• If 2r ≤ m² + 4m + 2, the algorithm produces a unique minimal decomposition

Eigenvector Counting Formula

Theorem 3.4: The number of eigenvectors of a general tensor M ∈ Hom(S^m V, ∧^a V):

• a = 1: (m^{n+1} - 1)/(m - 1)
• a = n-1: ((m+1)^{n+1} + (-1)^n)/(m + 2)

Experimental Setup

Implementation Platform

The paper provides Macaulay2 implementations, including:

1. Catalecticant Matrix Algorithm: File "cat method.m2"
2. Koszul Flattening Algorithm: File "General Kappa Method.m2"

Test Parameters

Catalecticant Matrix Method Success Range:

• n=2: (d=6, s≤8)
• n=3: (d=6, s≤16)
• n=4: (d=6, s≤16)

Koszul Method Success Range:

• n=2: (d=6, s≤7)
• n=3: (d=5, s≤11)
• n=4: (d=5, s≤14)

Experimental Results

Main Findings

1. Algorithm Effectiveness: Within theoretical boundaries, the algorithm successfully finds unique Waring decompositions
2. Computational Efficiency: Compared to brute force methods, the new algorithm completes the pentahedron example in less than 1 second, while brute force fails due to memory and time constraints
3. Boundary Accuracy: Experiments verify the accuracy of theoretical boundaries

Special Cases

1. Quintic Curves: Successfully decomposed as a sum of 7 fifth powers
2. Pentahedron: Successfully decomposed ternary cubic polynomials as a sum of 5 cubes
3. Rational Quartic Curves: As a byproduct, found a new representation of the unique rational quartic curve through 7 general points

Related Work

Classical Methods

1. Sylvester's Catalecticant Matrix Method: Developed in the 19th century, completely successful for binary cases
2. Alexander-Hirschowitz Theorem: Determines the rank of general symmetric tensors
3. Uniqueness Results: Work by Chiantini-Ciliberto and others

Modern Developments

1. Cartwright-Sturmfels: Eigenvector counting formulas for tensors
2. Brachat et al.: Numerical methods using semi-Hankel operators
3. Kolda-Mayo: Iterative computation methods for tensor eigenvectors

Conclusions and Discussion

Main Conclusions

1. Unified Framework: Provides a unified approach for handling classical uniqueness cases
2. Geometric Insights: Connects tensor decomposition with secant variety theory in algebraic geometry
3. Practical Algorithms: Develops implementable algorithms that guarantee success within specific ranges

Limitations

1. Applicable Scope: Algorithms succeed only when rank is sufficiently small and tensors are general
2. Computational Complexity: Problems remain difficult for large tensors
3. Numerical Stability: Requires further research on numerical method adaptation

Future Directions

1. Numerical Methods: GPU-accelerated eigenvector computation
2. Low-Rank Approximation: Small eigenvalue elimination methods analogous to matrix cases
3. More General Cases: Extension to partially symmetric tensors

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Successfully applies vector bundle techniques from algebraic geometry to tensor decomposition
2. Method Unification: Provides a unified treatment framework for multiple classical problems
3. Complete Implementation: Provides comprehensive algorithm implementation and testing
4. Precise Boundaries: Establishes precise theoretical boundaries for algorithm success

Weaknesses

1. Application Restrictions: Algorithm success range is relatively limited
2. Computational Complexity: Computation remains difficult for high-dimensional cases
3. Numerical Issues: Requires more work on rational number problems

Impact

1. Theoretical Contribution: Provides new geometric perspectives for tensor decomposition theory
2. Practical Value: Provides reliable algorithms within specific ranges
3. Foundation for Future Research: Provides basis for further numerical methods and GPU implementations

Applicable Scenarios

This method is particularly suitable for:

1. Small to medium-scale symmetric tensor decomposition
2. Theoretical research requiring exact decomposition
3. Algorithm development as a starting point and benchmark

This paper makes important theoretical and algorithmic contributions to the tensor decomposition field, particularly in pioneering new directions for applying algebraic geometry methods to practical computational problems.