Papers › Efficient Tensor Decomposition via Moment Matrix Extension
Efficient Tensor Decomposition via Moment Matrix Extension
Bobby Shi, Julia Lindberg, Joe Kileel
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Motivated by a flurry of recent work on efficient tensor decomposition algorithms, we show that the celebrated moment matrix extension algorithm of Brachat, Comon, Mourrain, and Tsigaridas for symmetric tensor canonical polyadic (CP) decomposition can be made efficient under the right conditions. We first show that the crucial property determining the complexity of the algorithm is the regularity of a target decomposition. This allows us to reduce the complexity of the vanilla algorithm, while also unifying results from previous works. We then show that for tensors in Sᵈℂⁿ⁺¹ with d even, low enough regularity can reduce finding a symmetric tensor decomposition to solving a system of linear equations. For order-$4$ tensors we prove that generic tensors of rank up to r=2n+1 can be decomposed efficiently via moment matrix extension, exceeding the rank threshold allowed by simultaneous diagonalization. We then formulate a conjecture that states for generic order-$4$ tensors of rank r=O(n²) the induced linear system is sufficient for efficient tensor decomposition, matching the asymptotics of existing algorithms and in fact improving the leading coefficient. Towards this conjecture we give computer assisted proofs that the statement holds for n=2, …, 17. Next we demonstrate that classes of nonidentifiable tensors can be decomposed efficiently via the moment matrix extension algorithm, bypassing the usual need for uniqueness of decomposition. Of particular interest is the class of monomials, for which the extension algorithm is not only efficient but also improves on existing theory by explicitly parameterizing the space of decompositions. Code for implementations of the efficient algorithm for generic tensors and monomials are provided, along with several numerical examples.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections