  In the tensor completion problem, one seeks to estimate a low-rank tensor
based on a random sample of revealed entries. In terms of the required sample
size, earlier work revealed a large gap between estimation with unbounded
computational resources (using, for instance, tensor nuclear norm minimization)
and polynomial-time algorithms. Among the latter, the best statistical
guarantees have been proved, for third-order tensors, using the sixth level of
the sum-of-squares (SOS) semidefinite programming hierarchy (Barak and Moitra,
2014). However, the SOS approach does not scale well to large problem
instances. By contrast, spectral methods --- based on unfolding or matricizing
the tensor --- are attractive for their low complexity, but have been believed
to require a much larger sample size.
  This paper presents two main contributions. First, we propose a new
unfolding-based method, which outperforms naive ones for symmetric $k$-th order
tensors of rank $r$. For this result we make a study of singular space
estimation for partially revealed matrices of large aspect ratio, which may be
of independent interest. For third-order tensors, our algorithm matches the SOS
method in terms of sample size (requiring about $rd^{3/2}$ revealed entries),
subject to a worse rank condition ($r\ll d^{3/4}$ rather than $r\ll d^{3/2}$).
We complement this result with a different spectral algorithm for third-order
tensors in the overcomplete ($r\ge d$) regime. Under a random model, this
second approach succeeds in estimating tensors of rank $d\le r \ll d^{3/2}$
from about $rd^{3/2}$ revealed entries.
