Exact tensor completion with sumofsquares
[edit]
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:16191673, 2017.
Abstract
We obtain the first polynomialtime algorithm for exact tensor completion that improves over the bound implied by reduction to matrix completion. The algorithm recovers an unknown 3tensor with $r$ incoherent, orthogonal components in $\mathbb R^n$ from $r⋅\tilde O(n^1.5)$ randomly observed entries of the tensor. This bound improves over the previous best one of $r⋅\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 sumofsquares method. The main technical challenge is to show that a small number of randomly chosen monomials are enough to construct a degree3 polynomial with precisely planted orthogonal global optima over the sphere and that this fact can be certified within the sumofsquares proof system.
Related Material


