On Polynomial Time Methods for Exact Low Rank Tensor Completion
  In this paper, we investigate the sample size requirement for exact recovery
of a high order tensor of low rank from a subset of its entries. We show that a
gradient descent algorithm with initial value obtained from a spectral method
can, in particular, reconstruct a ${d\times d\times d}$ tensor of multilinear
ranks $(r,r,r)$ with high probability from as few as
$O(r^{7/2}d^{3/2}\log^{7/2}d+r^7d\log^6d)$ entries. In the case when the ranks
$r=O(1)$, our sample size requirement matches those for nuclear norm
minimization (Yuan and Zhang, 2016a), or alternating least squares assuming
orthogonal decomposability (Jain and Oh, 2014). Unlike these earlier
approaches, however, our method is efficient to compute, easy to implement, and
does not impose extra structures on the tensor. Numerical results are presented
to further demonstrate the merits of the proposed approach.
