Title: Exact tensor completion with sum-of-squares,
Abstract: We obtain the first polynomial-time algorithm for exact tensor completion
that improves over the bound implied by reduction to matrix completion. The
algorithm recovers an unknown 3-tensor with $r$ incoherent, orthogonal
components in $\mathbb R^n$ from $r\cdot \tilde O(n^{1.5})$ randomly observed
entries of the tensor. This bound improves over the previous best one of
$r\cdot \tilde O(n^{2})$ by reduction to exact matrix completion. Our bound
also matches the best known results for the easier problem of approximate
tensor completion (Barak & Moitra, 2015).
Our algorithm and analysis extends seminal results for exact matrix
completion (Candes & Recht, 2009) to the tensor setting via the sum-of-squares
method. The main technical challenge is to show that a small number of randomly
chosen monomials are enough to construct a degree-3 polynomial with precisely
planted orthogonal global optima over the sphere and that this fact can be
certified within the sum-of-squares proof system.