Polynomial-Time Tensor Decompositions with Sum-of-Squares

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

Full description

Saved in:
Bibliographic Details
Main Authors: Tengyu Ma, Shi, Jonathan, Steurer, David
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Approximation algorithms
Computer science
Entropy
FOOBI algorithm
Lasserre hierarchy
Matrix decomposition
Robustness
simultaneous diagonalization
smoothed analysis
sum-of-squares method
Tensile stress
tensor decomposition
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0272-5428
DOI:10.1109/FOCS.2016.54