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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\varvec{d}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">d</mi> </mrow> </math></EquationSource> </InlineEquation> an order <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varvec{m}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">m</mi> </mrow> </math></EquationSource> </InlineEquation> of CP rank up to <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\varvec{\mathcal {O}}(\varvec{d}^{\lfloor \varvec{m/2}\rfloor })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-script">O</mi> </mrow> <mo stretchy="false">(</mo> <msup> <mrow> <mi mathvariant="bold-italic">d</mi> </mrow> <mrow> <mo>⌊</mo> <mrow> <mi mathvariant="bold-italic">m</mi> <mo mathvariant="bold" stretchy="false">/</mo> <mn mathvariant="bold">2</mn> </mrow> <mo>⌋</mo> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, 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 and Mayo (SIAM J. Matrix Anal. Appl. 32(4), 1095–1124 <CitationRef CitationID="CR31">2011</CitationRef>). 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.

Subspace power method for symmetric tensor decomposition

期刊论文
发表日期：

2025年8月2日

查看全文

Joe Kileel,
João M. Pereira

摘要

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 $\varvec{d}$ $d$ an order $\varvec{m}$ $m$ of CP rank up to $\varvec{\mathcal {O}}(\varvec{d}^{\lfloor \varvec{m/2}\rfloor })$ $O (d^{⌊ m / 2 ⌋})$ , 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 and Mayo (SIAM J. Matrix Anal. Appl. 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.