Subspace power method for symmetric tensor decomposition

Abstract

We introduce the Subspace Power Method (SPM) for calculating the CP decomposition of low-rank real symmetric tensors. This algorithm calculates one new CP component at a time, alternating between applying the shifted symmetric higher-order power method (SS-HOPM) to a certain modified tensor, constructed from a matrix flattening of the original tensor; and using appropriate deflation steps. We obtain rigorous guarantees for SPM regarding convergence and global optima for input tensors of dimension $d$ and order $m$ of CP rank up to $O(d^{\lfloor m/2\rfloor })$, via results in classical algebraic geometry and optimization theory. As a by-product of our analysis we prove that SS-HOPM converges unconditionally, settling a conjecture in [Kolda, T.G., Mayo, J.R.: Shifted power method for computing tensor eigenpairs. SIAM Journal on Matrix Analysis and Applications 32(4), 1095-1124 (2011)]. We present numerical experiments which demonstrate that SPM is efficient and robust to noise, being up to one order of magnitude faster than state-of-the-art CP decomposition algorithms in certain experiments. Furthermore, prior knowledge of the CP rank is not required by SPM.

arXiv comment36 pages

References in corpus (5)

• The Number of Eigenvalues of a Tensor
• Eigenvectors of tensors and algorithms for Waring decomposition
• Numerical Optimization for Symmetric Tensor Decomposition
• The condition number of join decompositions
• Overcomplete Independent Component Analysis via SDP

Cited by in corpus (5)

• Tensor decomposition for learning Gaussian mixtures from moments
• Symmetry Breaking in Symmetric Tensor Decomposition
• Robust Eigenvectors of Symmetric Tensors
• On a realization of motion and similarity group equivalence classes of labeled points in ${\mathbb{R}}^k$ with applications to computer vision
• Landscape analysis of an improved power method for tensor decomposition