Polynomial-time Tensor Decompositions with Sum-of-Squares

Abstract

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.

arXiv commentto appear in FOCS 2016

References in corpus (1)

• A Spectral Algorithm for Latent Dirichlet Allocation

Cited by in corpus (5)

• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use
• Learning Discrete Distributions from Untrusted Batches
• Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
• Convergence Rates of Latent Topic Models Under Relaxed Identifiability Conditions