A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
This provides a faster alternative to semidefinite programming methods for tensor decomposition, addressing a computational bottleneck in machine learning and signal processing, though it is incremental as it builds on prior work with similar guarantees.
The paper tackles the problem of decomposing overcomplete order-4 tensors with rank up to d^2, proposing a spectral algorithm that is robust to adversarial perturbations and runs in time O(n^2d^3), which is subquadratic in the input size d^4.
We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy 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 sum-of-squares semidefinite programming hierarchy (Ma, Shi, and Steurer STOC'16, arXiv:1610.01980), 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 linear-algebraic 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).