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$).
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.
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