A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:16831722, 2019.
Abstract
We give a spectral algorithm for decomposing overcomplete order4 tensors, so long as their components satisfy an algebraic nondegeneracy condition that holds for nearly all (all but an algebraic set of measure $0$) tensors over $(\mathbb{R}^d)^{\otimes 4}$ with rank $n \le d^2$. Our algorithm is robust to adversarial perturbations of bounded spectral norm. Our algorithm is inspired by one which uses the sumofsquares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC’16), and we achieve comparable robustness and overcompleteness guarantees under similar algebraic assumptions. However, our algorithm avoids semidefinite programming and may be implemented as a series of basic linearalgebraic operations. We consequently obtain a much faster running time than semidefinite programming methods: our algorithm runs in time $\tilde O(n^2d^3) \le \tilde O(d^7)$, which is subquadratic in the input size $d^4$ (where we have suppressed factors related to the condition number of the input tensor).
Related Material


