mlsanityData to 7 Oct 2026

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition

arXiv 2203.02790 ↗First posted 5 Mar 2022cs.LG cs.DS cs.NAcited by 7

Not on the map. Why?

Abstract (arXiv)

We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all but an algebraic set of measure 0) tensors over (ℝd)otimes 4 with rank n ≤ d2. Our algorithm is robust to adversarial perturbations of bounded spectral norm. Our algorithm is inspired by one which uses the sum-of-squares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC'16, arXiv:1610.01980), and we achieve comparable robustness and overcompleteness guarantees under similar algebraic assumptions. However, our algorithm avoids semidefinite programming and may be implemented as a series of basic linear-algebraic operations. We consequently obtain a much faster running time than semidefinite programming methods: our algorithm runs in time tilde O(n2d3) ≤ tilde O(d7), which is subquadratic in the input size d4 (where we have suppressed factors related to the condition number of the input tensor).

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

Builds on

16 of 47 references.

References · 16

  1. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  2. 2014A statistical model for tensor PCAcited by 72
  3. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  4. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  5. 2015Learning Mixtures of Gaussians in High Dimensionscited by 29
  6. 2017Bayesian estimation from few samples: community detection and related problemscited by 28
  7. 2014Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Methodcited by 22
  8. 2016LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Paincited by 22
  9. 2016Polynomial-time Tensor Decompositions with Sum-of-Squarescited by 22
  10. 2014Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updatescited by 21
  11. 2017On the Optimization Landscape of Tensor Decompositionscited by 21
  12. 2013Smoothed Analysis of Tensor Decompositionscited by 19
4 more
  1. 2017Fast and robust tensor decomposition with applications to dictionary learningcited by 14
  2. 2018On the Connection Between Learning Two-Layers Neural Networks and Tensor Decompositioncited by 14
  3. 2015Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithmscited by 10
  4. 2014Analyzing Tensor Power Method Dynamics in Overcomplete Regimecited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 1; 2024: 1; 2025: 0; 2026: 1.

7 papers.

  1. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  2. 2022Learning Polynomial Transformationscited by 3
  3. 2022Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Modelscited by 3
  4. 2023Symmetry & Critical Points for Symmetric Tensor Decomposition Problemscited by 3
  5. 2022Concentration of polynomial random matrices via Efron-Stein inequalitiescited by 0
  6. 2024Overcomplete Tensor Decomposition via Koszul-Young Flatteningscited by 0
  7. 2026Low-degree Lower bounds for clustering in moderate dimensioncited by 0