Average-Case Integrality Gap for Non-Negative Principal Component Analysis
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
复制标题
非负主成分分析的平均情况完整性差距
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Alexander S. Wein
中科院分区：
文献类型：
--
作者：
A. Bandeira;Dmitriy Kunisky;Alexander S. Wein
Montanari和Richard(2015)询问自然半定规划(SDP)松弛是否能有效地优化$\mathbf{x}^{\top}\mathbf{W}\mathbf{x}$over$\mathbf{x}\=1$，其中$x_i\geq 0$对于所有坐标$i$，其中$\mathbf{W}\in\mathbb{R}^{n\Times n}$取自高斯正交系综(GOE)或尖峰矩阵模型。在小型数值实验中，这种SDP对于GOE似乎是紧的，产生与最优向量$\mathbf{x}$对齐的一阶最优矩阵解。然而，我们证明了当$ntointy$时，SDP不是紧的，并且证明了关于该目标函数的一个上界不比简单谱上界$\lambda_{\max}(\mathbf{W})$好。我们还利用最近关于低次多项式假设检验的工具，提供了证据，证明没有亚指数时间认证算法可以改善这一行为。最后，我们给出了进一步的数值实验，估计在这种限制行为变得明显之前，$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 $\lambda_{\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.
DOI：
10.1214/18-aos1697
发表时间：
2015-09
期刊：
The Annals of Statistics
影响因子：
--
作者：
I. Johnstone;A. Onatski
通讯作者：
I. Johnstone;A. Onatski