Noisy Tensor Completion via the Sum-of-Squares Hierarchy

Boaz Barak, Ankur Moitra

In the noisy tensor completion problem we observe $m$ entries (whose location is chosen uniformly at random) from an unknown $n_1\times n_2\times n_3$ tensor $T$. We assume that…