Exact tensor completion with sum-of-squares

Understand

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).