# Fast algorithm for overcomplete order-3 tensor decomposition

arXiv: https://arxiv.org/abs/2202.06442 · HTML: https://mlsanity.com/paper/2202.06442/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 38 references that are in the map.
- First posted on arXiv 14 Feb 2022.

## Builds on (most cited first, 15 of 15)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014)
- [LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain](https://mlsanity.com/paper/1607.03463/) (2016)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Fast and robust tensor decomposition with applications to dictionary learning](https://mlsanity.com/paper/1706.08672/) (2017)
- [Subspace power method for symmetric tensor decomposition](https://mlsanity.com/paper/1912.04007/) (2019)
- [Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor](https://mlsanity.com/paper/1708.05622/) (2017)
- [Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms](https://mlsanity.com/paper/1504.05287/) (2015)
- [Tensor Decompositions in Deep Learning](https://mlsanity.com/paper/2002.11835/) (2020)
- [Landscape analysis of an improved power method for tensor decomposition](https://mlsanity.com/paper/2110.15821/) (2021)
- [Spectral Methods from Tensor Networks](https://mlsanity.com/paper/1811.00944/) (2018)

## Built on by (most cited first, 5 of 5)

- [Tensor cumulants for statistical inference on invariant distributions](https://mlsanity.com/paper/2404.18735/) (2024)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Causal Discovery in Mixtures of Populations](https://mlsanity.com/paper/2311.07454/) (2023)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)

## Abstract (arXiv)

We develop the first fast spectral algorithm to decompose a random third-order tensor over ℝd of rank up to O(d3/2/polylog(d)). Our algorithm only involves simple linear algebra operations and can recover all components in time O(d6.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(d4/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.