Exact tensor completion with sum-of-squares
Aaron Potechin Institute for Advanced Study. Supported by the Simons Collaboration for Algorithms and Geometry and by the NSF under agreement No. CCF-1412958. Part of this work was done while at Cornell University. David Steurer Institute for Advanced Study and Cornell University, Supported by a Microsoft Research Fellowship, a Alfred P. Sloan Fellowship, NSF awards (CCF-1408673,CCF-1412958,CCF-1350196), and the Simons Collaboration for Algorithms and Geometry.
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\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).
中文速览
精确张量补全（exact tensor completion）问题长期以来只能靠"先把张量展平成矩阵再套矩阵补全算法"来处理，导致采样复杂度高达 r·Õ(n²)。本文提出了第一个真正突破这一瓶颈的多项式时间算法：对于一个由 r 个非相干正交分量构成的三阶张量，只需观测 r·Õ(n¹·⁵) 个随机位置的条目就能精确恢复全部内容。核心方法是平方和（Sum-of-Squares, SoS）半正定规划框架——作者将矩阵补全中的对偶证书构造技术推广到张量场景，证明了随机选取的少量单项式就足以在球面上构造一个恰好在目标正交分量处达到全局最优的三线性型，并且这一事实可在 SoS 证明系统内被有效验证，从而把唯一性证明直接转化为高效重建算法。这一结果不仅与此前近似张量补全的最优已知样本界相匹配，也为把 SoS 方法系统性地用于精确恢复推断问题提供了新范式。
原文 arXiv:1702.06237;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1702.06237v3