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

Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein

Abstract

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.

Introduction

Principal Component Analysis (PCA) is a fundamental tool in data science, used to identify the primary directions of variance within a dataset. In many scientific domains—such as gene expression analysis or hyperspectral imaging—the underlying signals are known to be non-negative. This physical constraint leads to the problem of Non-Negative PCA (NN-PCA).

While standard PCA is computationally efficient (solvable via the top eigenvector), the addition of non-negativity constraints transforms the problem into one that is NP-hard in the worst case. To bridge this gap, researchers often turn to Semidefinite Programming (SDP) relaxations. These relaxations transform the hard, non-convex constraint into a convex one that can be solved in polynomial time. Previous literature, specifically work by Montanari and Richard (2015), suggested that for random matrices, this SDP relaxation might be "tight," meaning it would consistently find the true optimal solution. This paper investigates whether that perceived efficacy holds as problem sizes scale toward the high-dimensional limit.

The Theoretical Integrality Gap

The core contribution of this research is a rigorous proof that the SDP relaxation for NN-PCA fails to be tight as the dimension $n$ grows. By analyzing a random matrix $W$ drawn from the Gaussian Orthogonal Ensemble (GOE), the authors demonstrate a persistent "integrality gap."

Specifically, the true maximum value of the NN-PCA objective on such a matrix is known to converge to $\sqrt{2}$ as $n \to \infty$. However, the authors prove that the value of the SDP relaxation converges to $2$. This means the SDP provides a certification bound that is no better than the standard spectral bound (the maximum eigenvalue $\lambda_{\max}(W)$), which ignores the non-negativity constraint entirely.

To prove this lower bound, the authors developed a "nudging" technique. They constructed a feasible solution for the SDP by taking the top eigenvectors of the noise matrix and shifting them using an all-ones matrix. This construction demonstrates that the SDP remains "stuck" at a value of 2, even when the actual non-negative maximum is significantly lower.

Computational Hardness and Low-Degree Polynomials

Beyond analyzing a specific SDP, the paper addresses whether any efficient algorithm could potentially close this gap. Using the Low-Degree Polynomial Method, the authors provide evidence for a fundamental computational barrier. This framework analyzes the ability of polynomial functions to distinguish between pure noise (GOE) and a "signal + noise" model (the spiked Wigner model).

Their analysis suggests that improving upon the spectral bound of 2 would require solving a problem that is conjectured to be hard for all subexponential-time algorithms. This implies that the failure of the SDP is not a specific weakness of the relaxation itself, but rather a reflection of an inherent statistical-to-computational gap in the NN-PCA problem.

The "Laptop Scale" Illusion

One of the most striking aspects of this study is the explanation of why previous numerical experiments suggested the SDP was tight. In small-scale simulations (e.g., $n \approx 150$), the SDP often produces a rank-one solution that appears optimal. The authors characterize this as a "deceptive finite-size effect."

By developing a "witness" construction to simulate SDP behavior at much larger scales ($n = 30,000$), the authors show that the tightness observed on a "laptop scale" begins to vanish as $n$ increases. Their numerical results suggest that the crossover point—where the SDP's failure becomes clearly evident—occurs around $n \approx 10^4$. Because solving an SDP at such a high dimension is computationally prohibitive for standard hardware, the asymptotic failure of the method remained hidden behind the success of small-scale tests.

Conclusion

This paper serves as a cautionary tale for high-dimensional optimization. It demonstrates that the empirical success of an algorithm in low dimensions does not always guarantee its performance at scale. For Non-Negative PCA, the natural SDP relaxation eventually reverts to the simple spectral bound, and evidence from the low-degree polynomial method suggests that this limitation may be unavoidable for all efficient certification algorithms. Future work may explore whether higher-order Sum-of-Squares (SoS) relaxations can break this barrier, though the current findings suggest that the computational landscape of non-negative constraints is significantly more challenging than previously assumed.

Summary updated

Abstract

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.
BibTeX
@inproceedings{bandeira2021average,
  author = {Afonso S. Bandeira and Dmitriy Kunisky and Alexander S. Wein},
  title = {{Average-Case Integrality Gap for Non-Negative Principal Component Analysis}},
  booktitle = {MSML},
  year = {2021},
  url = {https://openreview.net/forum?id=0gQOUW7Opx},
}
Figure