Name
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 $rcdot tilde O(n^{1.5})$ randomly observed entries of the tensor. This bound improves over the previous best one of $rcdot tilde O(n^{2})$ by reduction to exact matrix completion. bound also matches the best known results for the easier problem of approximate tensor completion (Barak u0026 Moitra, 2015). Our algorithm and analysis extends seminal results for exact matrix completion (Candes u0026 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 a precisely planted orthogonal global optima over the sphere and that this fact can be certified within the sum-of-squares proof system. |
Year | Venue | DocType |
|---|---|---|
2017 | COLT | Conference |
Volume | Citations | PageRank |
abs/1702.06237 | 5 | 0.44 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aaron Potechin | 1 | 63 | 7.81 |
| David Steurer | 2 | 934 | 44.91 |