Tensor principal component analysis via sum-of-squares proofs
  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 \geq 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 \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 $A$. The previous best algorithms with
provable guarantees required $\tau \geq \Omega(n)$.
  In the regime $\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-$4$ sum-of-squares relaxations of the
maximum-likelihood-estimation problem for the statistical model. To complement
our algorithmic results, we show that degree-$4$ sum-of-squares relaxations
break down for $\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.
