mlsanityData to 7 Oct 2026

Fast algorithm for overcomplete order-3 tensor decomposition

arXiv 2202.06442 ↗First posted 14 Feb 2022cs.LG cs.DScited by 5

Not on the map. Why?

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.

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

Builds on

15 of 38 references.

References · 15

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 223
  3. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  4. 2017Introduction to Tensor Decompositions and their Applications in Machine Learningcited by 45
  5. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  6. 2014Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Methodcited by 22
  7. 2016LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Paincited by 22
  8. 2016Polynomial-time Tensor Decompositions with Sum-of-Squarescited by 22
  9. 2017Fast and robust tensor decomposition with applications to dictionary learningcited by 14
  10. 2019Subspace power method for symmetric tensor decompositioncited by 14
  11. 2017Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensorcited by 13
  12. 2015Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithmscited by 10
3 more
  1. 2020Tensor Decompositions in Deep Learningcited by 9
  2. 2021Landscape analysis of an improved power method for tensor decompositioncited by 7
  3. 2018Spectral Methods from Tensor Networkscited by 6

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 1; 2024: 2.

5 papers.

  1. 2024Tensor cumulants for statistical inference on invariant distributionscited by 8
  2. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  3. 2022Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Modelscited by 3
  4. 2023Causal Discovery in Mixtures of Populationscited by 3
  5. 2024Overcomplete Tensor Decomposition via Koszul-Young Flatteningscited by 0