# Average-Case Integrality Gap for Non-Negative Principal Component Analysis

arXiv: https://arxiv.org/abs/2012.02243 · HTML: https://mlsanity.com/paper/2012.02243/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2020.

## Built on by (most cited first, 2 of 2)

- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes](https://mlsanity.com/paper/2112.12306/) (2021)

## Abstract (arXiv)

Montanari and Richard (2015) asked whether a natural semidefinite programming (SDP) relaxation can effectively optimize xtopW x over |x| = 1 with xi ≥ 0 for all coordinates i, where W ∈ ℝn × 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 x. We prove, however, that as n → ∞ the SDP is not tight, and certifies an upper bound asymptotically no better than the simple spectral bound λmax(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.