# Polynomial-time Tensor Decompositions with Sum-of-Squares

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

## Key facts

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

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

- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms](https://mlsanity.com/paper/1802.07417/) (2018)
- [Estimation Contracts for Outlier-Robust Geometric Perception](https://mlsanity.com/paper/2208.10521/) (2022)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Fast algorithm for overcomplete order-3 tensor decomposition](https://mlsanity.com/paper/2202.06442/) (2022)
- [Closed-Loop Transcription via Convolutional Sparse Coding](https://mlsanity.com/paper/2302.09347/) (2023)
- [Dictionary Learning for the Almost-Linear Sparsity Regime](https://mlsanity.com/paper/2210.10855/) (2022)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond](https://mlsanity.com/paper/2212.03851/) (2022)
- [Conditional Linear Regression for Heterogeneous Covariances](https://mlsanity.com/paper/2111.07834/) (2021)
- [Polynomial-time Sparse Measure Recovery: From Mean Field Theory to Algorithm Design](https://mlsanity.com/paper/2204.07879/) (2022)
- [Tensor Methods in High Dimensional Data Analysis: Opportunities and Challenges](https://mlsanity.com/paper/2405.18412/) (2024)
- [Rotated Mean-Field Variational Inference and Iterative Gaussianization](https://mlsanity.com/paper/2510.07732/) (2025)
- [Robust Mean Estimation Without Moments for Symmetric Distributions](https://mlsanity.com/paper/2302.10844/) (2023)
- [Computational Lower Bounds for Regret Minimization in Normal-Form Games](https://mlsanity.com/paper/2411.01721/) (2024)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)
- [Federated Independent Component Analysis via Spectral Alignment and Robust Aggregation](https://mlsanity.com/paper/2505.20532/) (2025)
- [Low-degree Lower bounds for clustering in moderate dimension](https://mlsanity.com/paper/2602.23023/) (2026)

## 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.