Tensor principal component analysis via sum-of-squares

COLT 2015.



We study a statistical model for the introduced by Montanari and Richard: Given a order-33 tensor TT of the form T=τv03+AT = \tau \cdot v_0^{\otimes 3} + A, where τ0\tau \geq 0 is a signal-to-noise ratio, v0v_0 is a unit vector, and AA is a random noise tensor, the goal is to recover the planted vector v0v_0. For the case that AA has iid standard Gaussian entries, we give an efficient algorithm to recover v0v_0 whenever τω(n3/4log(n)1/4)\tau \geq \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 AA. The previous best algorithms with provable guarantees required τΩ(n)\tau \geq \Omega(n).

In the regime τo(n)\tau \leq o(n), natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down (in the sense that their integrality gap is large). To go beyond this barrier, we use convex relaxations based on the sum-of-squares method. Our recovery algorithm proceeds by rounding a degree-44 sum-of-squares relaxations of the maximum-likelihood-estimation problem for the statistical model. To complement our algorithmic results, we show that degree-44 sum-of-squares relaxations break down for τO(n3/4/log(n)1/4)\tau \leq O(n^{3/4}/\log(n)^{1/4}), which demonstrates that improving our current guarantees (by more than logarithmic factors) would require new techniques or might even be intractable.

Finally, we show how to exploit additional problem structure in order to solve our sum-of-squares relaxations, up to some approximation, very efficiently. Our fastest algorithm runs in nearly-linear time using shifted (matrix) power iteration and has similar guarantees as above. The analysis of this algorithm also confirms a variant of a conjecture of Montanari and Richard about singular vectors of tensor unfoldings.