A Robust Spectral Algorithm for Overcomplete Tensor Decomposition

Abstract

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^2{d}^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).

arXiv comment60 pages, 4 figures, ACM Annual Workshop on Computational Learning Theory 2019

Cited by in corpus (6)

• Computational Barriers to Estimation from Low-Degree Polynomials
• Symmetry Breaking in Symmetric Tensor Decomposition
• Efficient Tensor Decomposition
• SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation
• Conditional Linear Regression for Heterogeneous Covariances
• Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS