Polynomial-Time Tensor Decompositions with Sum-of-Squares

By Tengyu Ma, Jonathan Shi, David Steurer. 2016

130 citations recorded by the source corpus.

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-squaresrelaxations with spectral analogs of maximum entropy constraints.

Subfields: Computational Mathematics, Computational Mechanics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

1. Jerry Zheng Li
2. David Steurer
3. Samuel B. Hopkins
4. Pravesh Kothari
5. Rong Ge
6. Raghu Meka
7. Yuanzhi Li
8. Zeyuan Allen-Zhu

In Computational Mechanics

1. Pravesh Kothari
2. Jerry Zheng Li
3. Samuel B. Hopkins
4. Mingda Qiao
5. Rong Ge
6. Adam R. Klivans
7. Raghu Meka
8. Gregory Valiant

In Signal Processing

1. Jerry Zheng Li
2. Samuel B. Hopkins
3. Pravesh Kothari
4. Gregory Valiant
5. David Steurer
6. Rong Ge
7. Raghu Meka
8. Anima Anandkumar

Citations in the corpus

• Learning Discrete Distributions from Untrusted Batches (2017, background): “…efficient algorithms for returning good (in a competitive-analysis sense) low-rank approximations of matrices in the ℓ 1 norm [SWZ17], and for efficiently recovering low-rank approximations of special classes of tensors, including those with random or “incoherent” factors (see e.g. [Kru77, MSS16]).”
• Outlier-robust moment-estimation via sum-of-squares (2017, methodology): “(Often, a key ingredient of these algorithms in the high-dimensional setting is tensor decomposition [MR05, AFH + 12, AGH + 14, HK13b, BCMV14, BKS15, GM15, MSS16a].)”
• Efficient Algorithms for Outlier-Robust Regression (2018, result): “At a high level, our approach resembles several recent works (Ma et al., 2016; Barak and Moitra, 2016; Potechin and Steurer, 2017; Kothari and Steurer, 2017; Hopkins and Li, 2017) starting with the pioneering work of Barak et al.”
• Learning Two-layer Neural Networks with Symmetric Inputs (2018, methodology): “We use the ideas similar to Bhaskara et al. (2014) and Ma et al. (2016).”
• Mixture models, robustness, and sum of squares proofs (2017, methodology): “There has been much recent interest in using the SoS method to solve unsupervised learning problems in generative models [7, 8, 31, 36, 49, 56].”