Exact tensor completion with sum-of-squares

Aaron Potechin, David Steurer
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1619-1673, 2017.

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⋅\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 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-potechin17a, title = {Exact tensor completion with sum-of-squares}, author = {Potechin, Aaron and Steurer, David}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1619--1673}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/potechin17a/potechin17a.pdf}, url = {https://proceedings.mlr.press/v65/potechin17a.html}, 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⋅\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 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.} }
Endnote
%0 Conference Paper %T Exact tensor completion with sum-of-squares %A Aaron Potechin %A David Steurer %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-potechin17a %I PMLR %P 1619--1673 %U https://proceedings.mlr.press/v65/potechin17a.html %V 65 %X 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⋅\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 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.
APA
Potechin, A. & Steurer, D.. (2017). Exact tensor completion with sum-of-squares. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1619-1673 Available from https://proceedings.mlr.press/v65/potechin17a.html.

Related Material