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

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.