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.

该研究提出了基于展开的新方法，其中一个应用是特征空间估计。研究者针对张量完成问题，提出了两种方法，一种是采用 SOS 方法，但不适合处理大规模问题；另一种是采用展开或者矩阵分解方法，在解决三阶张量问题时性能和 SOS 方法相当。