Numerical optimization for symmetric tensor decomposition

Tamara G. Kolda

Abstract

This paper investigates numerical optimization techniques for the decomposition of real-valued symmetric tensors into a sum of symmetric outer products. By comparing various optimization formulations, including weighted and unweighted error functions and penalty terms for normalization, the study demonstrates that standard numerical methods are robust to noise and scalable. A key finding is that ignoring symmetry during the optimization process and symmetrizing the result post-hoc is often more efficient than direct symmetric optimization.

Introduction

In linear algebra, the decomposition of symmetric matrices into eigenvalues and eigenvectors is a fundamental tool. Symmetric tensor decomposition is the higher-order generalization of this task: taking an $m$-way array (where entries are identical under any permutation of indices) and expressing it as a sum of symmetric outer products ($x \circ x \circ \dots \circ x$).

Symmetric tensor decomposition of A into a sum of p symmetric rank-1 components.

While algebraic methods exist for this problem, they are often designed for complex-valued tensors and struggle with real-valued constraints, noise, or large-scale data. This work addresses the gap in practical, scalable, and robust numerical methods for real-valued symmetric decomposition, covering both unconstrained and nonnegative cases.

Methodology

Several optimization strategies are compared to find the most effective way to recover low-rank structures:

  • Weighted vs. Unweighted Formulations: The study examines whether it is better to minimize the error over every single entry of the tensor (weighted by multiplicity due to symmetry) or just over the unique entries.
  • Penalty Terms: To handle scaling ambiguity, where a scalar can be moved between the weight $\lambda$ and the vector $x$, a penalty term is introduced to encourage vectors to have a unit norm. This normalization makes the optimization landscape better behaved and prevents the Jacobian from becoming singular.
  • Rank Determination: When the rank $p$ is unknown, an approximate $\ell_1$ penalty on component weights is used to encourage sparsity, effectively "turning off" unnecessary components.

The "Lazy" Approach to Symmetry

Perhaps the most significant methodological insight is that symmetry can be treated as "optional" during the main computation. By treating the symmetric tensor as a general tensor and using standard Canonical Polyadic (CP) decomposition (like Alternating Least Squares), solvers can leverage highly optimized non-symmetric algorithms. The result is then "symmetrized" afterward.

General Canonical Polyadic (CP) decomposition, where symmetry is not explicitly enforced during optimization.

Experimental Results

The study utilized synthetic datasets to test challenges such as varying noise levels, high dimensions, and collinearity (where underlying vectors are nearly parallel). Key findings include:

  • Efficiency: The "CP-ALS + Symmetrization" approach was often 10x faster than direct symmetric optimization while maintaining high accuracy.
  • Robustness: Numerical optimization proved much more stable than traditional algebraic methods when data was contaminated with noise.
  • Gradient Speedup: For larger tensors, using a specialized gradient expression provided a 5-15x speedup over generic implementations.
  • Nonnegativity: The methods adapted seamlessly to nonnegative symmetric tensors (completely positive tensors), showing that standard bound-constrained optimization is a strong baseline.

Conclusion and Future Work

While numerical optimization is robust, the problem remains non-convex, requiring multiple random starting points to ensure a global minimum is found. Future work aims to refine rank selection through statistical validation (like cross-validation) and to address the computational challenges of decomposing very high-rank, high-dimensional tensors in "big data" contexts.

Summary updated

Abstract

We consider the problem of decomposing a real-valued symmetric tensor as the sum of outer products of real-valued vectors. Algebraic methods exist for computing complex-valued decompositions of symmetric tensors, but here we focus on real-valued decompositions, both unconstrained and nonnegative, for problems with low-rank structure. We discuss when solutions exist and how to formulate the mathematical program. Numerical results show the properties of the proposed formulations (including one that ignores symmetry) on a set of test problems and illustrate that these straightforward formulations can be effective even though the problem is nonconvex.
BibTeX
@article{kolda2015numerical,
  author = {Tamara G. Kolda},
  title = {{Numerical optimization for symmetric tensor decomposition}},
  journal = {Math. Program.},
  year = {2015},
  doi = {10.1007/s10107-015-0895-0},
}
Figure