论文标题
非阴性主组件分析的平均案例完整性差距
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
论文作者
论文摘要
Montanari和Richard（2015）询问了自然的半决赛编程（SDP）放松是否可以有效地优化$ \ Mathbf {x}^{\ top} \ top} \ Mathbf {w} \ Mathbf {x} $ iver $ \ | \ | \ | \ | \ | \ | \ | \ | = 1 $ with $ x_i \ geq 0 $ for All Coordinates $ i $，其中$ \ Mathbf {w} \ in \ Mathbb {r}^{n \ times n} $是从高斯正交共奏（goe）或尖刺的矩阵模型中绘制的。在小型数值实验中，该SDP对于GOE来说似乎很紧，产生了与最佳矢量$ \ mathbf {x} $对齐的排名最佳矩阵解决方案。但是，我们证明，作为$ n \ to \ infty $，SDP并不紧密，并且在此目标函数上证明上限渐近差不多。我们还提供了使用最新文献中有关假设测试的工具的证据，表明没有次指数时间认证算法可以改善这种行为。最后，我们提出了进一步的数值实验，以估计在这种限制行为变得明显之前需要大大的$ n $，从而提供了一个警告性的例子，以防止在小小的“笔记本电脑尺度”计算中从其功效中推断出高度的SDP的渐近渐近学。
Montanari and Richard (2015) asked whether a natural semidefinite programming (SDP) relaxation can effectively optimize $\mathbf{x}^{\top}\mathbf{W} \mathbf{x}$ over $\|\mathbf{x}\| = 1$ with $x_i \geq 0$ for all coordinates $i$, where $\mathbf{W} \in \mathbb{R}^{n \times n}$ is drawn from the Gaussian orthogonal ensemble (GOE) or a spiked matrix model. In small numerical experiments, this SDP appears to be tight for the GOE, producing a rank-one optimal matrix solution aligned with the optimal vector $\mathbf{x}$. We prove, however, that as $n \to \infty$ the SDP is not tight, and certifies an upper bound asymptotically no better than the simple spectral bound $λ_{\max}(\mathbf{W})$ on this objective function. We also provide evidence, using tools from recent literature on hypothesis testing with low-degree polynomials, that no subexponential-time certification algorithm can improve on this behavior. Finally, we present further numerical experiments estimating how large $n$ would need to be before this limiting behavior becomes evident, providing a cautionary example against extrapolating asymptotics of SDPs in high dimension from their efficacy in small "laptop scale" computations.
