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.

研究了一个针对张量主成分分析问题的统计模型，通过基于四次幂和松弛的舍入算法，证明了随机噪声张量的种植向量可以在高概率下被回收，还证明了四次幂和松弛在一定程度下是不起作用的，研究并利用了额外的问题结构来求解我们的平方和松弛。