Abstract

We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order- $3$ tensor $T$ of the form $T=\tau\cdot v_{0}^{\otimes 3}+A$ , where $\tau\geqslant 0$ is a signal-to-noise ratio, $v_{0}$ is a unit vector, and $A$ is a random noise tensor, the goal is to recover the planted vector $v_{0}$ . For the case that $A$ has iid standard Gaussian entries, we give an efficient algorithm to recover $v_{0}$ whenever $\tau\geqslant\omega(n^{3/4}\log(n)^{1/4})$ , and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of $A$ . The previous best algorithms with provable guarantees required $\tau\geqslant\Omega(n)$ .