mlsanityData to 7 Oct 2026

Polynomial-time Tensor Decompositions with Sum-of-Squares

arXiv 1610.01980 ↗First posted 6 Oct 2016cs.DS cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

We give new algorithms based on the sum-of-squares method for tensor decomposition. Our results improve the best known running times from quasi-polynomial to polynomial for several problems, including decomposing random overcomplete 3-tensors and learning overcomplete dictionaries with constant relative sparsity. We also give the first robust analysis for decomposing overcomplete 4-tensors in the smoothed analysis model. A key ingredient of our analysis is to establish small spectral gaps in moment matrices derived from solutions to sum-of-squares relaxations. To enable this analysis we augment sum-of-squares relaxations with spectral analogs of maximum entropy constraints.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Oct 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 0; 2020: 0; 2021: 4; 2022: 8; 2023: 3; 2024: 3; 2025: 2; 2026: 1.

22 papers.

Sort:

By area:

  1. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  2. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  3. 2018Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithmscited by 13
  4. 2022Estimation Contracts for Outlier-Robust Geometric Perceptioncited by 11
  5. 2021SoS Degree Reduction with Applications to Clustering and Robust Moment Estimationcited by 7
  6. 2021The Complexity of Sparse Tensor PCAcited by 7
  7. 2022A Robust Spectral Algorithm for Overcomplete Tensor Decompositioncited by 7
  8. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  9. 2022Fast algorithm for overcomplete order-3 tensor decompositioncited by 5
  10. 2023Closed-Loop Transcription via Convolutional Sparse Codingcited by 4
  11. 2022Dictionary Learning for the Almost-Linear Sparsity Regimecited by 3
  12. 2022Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Modelscited by 3
10 more
  1. 2022Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyondcited by 2
  2. 2021Conditional Linear Regression for Heterogeneous Covariancescited by 1
  3. 2022Polynomial-time Sparse Measure Recovery: From Mean Field Theory to Algorithm Designcited by 1
  4. 2024Tensor Methods in High Dimensional Data Analysis: Opportunities and Challengescited by 1
  5. 2025Rotated Mean-Field Variational Inference and Iterative Gaussianizationcited by 1
  6. 2023Robust Mean Estimation Without Moments for Symmetric Distributionscited by 0
  7. 2024Computational Lower Bounds for Regret Minimization in Normal-Form Gamescited by 0
  8. 2024Overcomplete Tensor Decomposition via Koszul-Young Flatteningscited by 0
  9. 2025Federated Independent Component Analysis via Spectral Alignment and Robust Aggregationcited by 0
  10. 2026Low-degree Lower bounds for clustering in moderate dimensioncited by 0