Fast algorithm for overcomplete order-3 tensor decomposition

2022/02/14 by Jingqiu Ding, Ding, Jingqiu, Tommaso d'Orsi +7
Computer Science · Mathematics · #Advanced Neural Network Applications #Computational Physics and Python Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2202.06442

openalex publication_date 2022/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We develop the first fast spectral algorithm to decompose a random third-order tensor over ℝ^d of rank up to O(d^3/2/polylog(d)). Our algorithm only involves simple linear algebra operations and can recover all components in time O(d^6.05) under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most O(d^4/3/polylog(d)). Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm.

Related

• Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Spectral algorithms for tensor completion