Polynomial-time Tensor Decompositions with Sum-of-Squares
This addresses computational bottlenecks in machine learning and data analysis by offering faster, polynomial-time solutions for tensor decomposition, which is incremental but impactful for specific domains.
The paper tackles tensor decomposition problems by developing new sum-of-squares algorithms that improve running times from quasi-polynomial to polynomial for tasks like decomposing random overcomplete 3-tensors and learning overcomplete dictionaries with constant relative sparsity, and provides the first robust analysis for overcomplete 4-tensors in smoothed analysis.
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.