Tensor principal component analysis via sum-of-squares proofs
Samuel B. Hopkins Department of Computer Science, Cornell University. Please direct all communication to D.S. Jonathan Shi David Steurer
Abstract
We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order- $3$ tensor $T$ of the form $T=\tau\cdot v_{0}^{\otimes 3}+A$ , where $\tau\geqslant 0$ is a signal-to-noise ratio, $v_{0}$ is a unit vector, and $A$ is a random noise tensor, the goal is to recover the planted vector $v_{0}$ . For the case that $A$ has iid standard Gaussian entries, we give an efficient algorithm to recover $v_{0}$ whenever $\tau\geqslant\omega(n^{3/4}\log(n)^{1/4})$ , and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of $A$ . The previous best algorithms with provable guarantees required $\tau\geqslant\Omega(n)$ .
中文速览
张量主成分分析（Tensor PCA）是一个经典难题：在一个被高斯噪声污染的三阶张量中，如何高效地找回隐藏的信号向量？此前最好的有理论保证的算法需要信噪比 τ 达到 Ω(n) 才能奏效，而信息论下界显示 τ ≥ ω(√n) 就已足够，两者之间存在巨大鸿沟。本文借助"平方和"（Sum-of-Squares，SoS）方法——一种基于半正定规划的凸松弛框架——设计了新算法，将有效恢复的信噪比门槛降低至 τ ≥ ω(n^{3/4} log(n)^{1/4})，大幅缩小了这一鸿沟；同时还证明，在同等复杂度的 SoS 框架内，τ ≤ O(n^{3/4}/log(n)^{1/4}) 时算法必然失效，说明当前结果在这一方法论下几乎最优。此外，作者进一步将 SoS 松弛近似求解转化为近线性时间的"移位矩阵幂迭代"算法，使算法真正具备实用性，也验证了 Montanari 和 Richard 关于张量展开奇异向量的一个猜想，为理解高阶统计推断的计算复杂性提供了重要工具。
原文 arXiv:1507.03269;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1507.03269v1