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.

本文基于平方和方法给出了用于张量分解的新算法，结果改进了多个问题的运行时间，包括对超完备三元组分解和具有常数相对稀疏度的超完备字典的学习等问题的算法，同时首次在平滑分析模型中给出了超完备四元组分解的稳健性分析。而此分析的关键因素在于在由平方和松弛解导出的矩阵时刻中建立小的谱间隙，为了使此分析成为可能，本文将最大熵约束的谱同构加到平方和松弛约束上。