Abstract
Montanari and Richard (2015) asked whether a natural semidefinite programming (SDP) relaxation can effectively optimize $\bx^{\top}\bW \bx$ over $\|\bx\| = 1$ with $x_i \geq 0$ for all coordinates $i$, where $\bW \in \RR^{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 $\bx$. 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}(\bW)$ 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 cornerstone of dimensionality reduction and data analysis. In many practical applications, such as genomics, imaging, and document clustering, the underlying components are known to be non-negative. Incorporating this constraint into PCA can significantly improve interpretability and accuracy. However, while standard PCA is easily solved via eigendecomposition, adding a non-negativity constraint transforms the problem into an NP-hard optimization challenge.
To address this, researchers often turn to Semidefinite Programming (SDP) relaxations. These methods lift the vector-based optimization into a higher-dimensional matrix space, creating a convex problem that can be solved in polynomial time. A prominent study by Montanari and Richard (2015) suggested that for random matrices, these SDPs might be "tight"—meaning the relaxation provides the exact solution to the original non-convex problem. This paper re-evaluates that optimism, demonstrating that the perceived success of SDPs in small-scale experiments is a deceptive artifact of low dimensionality.
The Non-Negative PCA Problem
The core objective is to maximize the quadratic form $\bx^{\top}\bW \bx$ subject to the constraints $\|\bx\| = 1$ and $x_i \geq 0$ for all $i$. When $\bW$ is drawn from the Gaussian Orthogonal Ensemble (GOE), the true maximum value of this objective, denoted as $\lambda_+(\bW)$, is known to converge to $\sqrt{2}$ as $n \to \infty$.
In contrast, the standard spectral bound (ignoring the non-negativity constraint) is the maximum eigenvalue $\lambda_{\max}(\bW)$, which converges to $2$. The central question is whether an SDP relaxation can "certify" a bound closer to $\sqrt{2}$ than to $2$. If the SDP value is close to $\sqrt{2}$, it is considered tight; if it remains near $2$, it fails to leverage the non-negativity constraint effectively.
Theoretical Results: The Integrality Gap
The authors provide a rigorous proof that the SDP relaxation fails to outperform the simple spectral bound in the high-dimensional limit.
Theorem 4 establishes that for a GOE matrix $\bW$, the value of the SDP relaxation converges to $2$ with high probability as $n \to \infty$. This reveals an "integrality gap" of $\sqrt{2}$. While the true non-negative maximum is $\sqrt{2}$, the SDP relaxation claims it is $2$.
To prove this, the authors construct a "primal witness"—a specific matrix that satisfies all SDP constraints while achieving an objective value near $2$. This construction demonstrates that the SDP's feasible region is too large, containing high-value solutions that do not correspond to any valid non-negative vector.
The Computational Barrier
Beyond the specific failure of the natural SDP, the paper investigates whether any efficient algorithm could do better. Using the Low-Degree Polynomial Method, the authors provide evidence that this failure is not unique to the SDP but represents a fundamental computational wall.
They show that certifying a bound better than the spectral limit is related to a hard hypothesis testing problem: distinguishing a standard Wishart matrix from a Spiked Wishart model with a negative spike. Based on this reduction, Conjecture 7 suggests that no algorithm running in subexponential time ($exp(O(n^{1-\eta}))$) can certify an upper bound better than $2 - \epsilon$. This suggests a sharp distinction between recovery (finding a good non-negative vector) and certification (proving no better vector exists).
The Illusion of Small Scale
One of the most significant contributions of this work is explaining why previous numerical studies reached different conclusions. In experiments with $n \approx 150$ (typical "laptop scale" computations), the SDP often appears rank-one and perfectly tight.
However, the authors' numerical simulations and theoretical bounds show that the transition from "tight" to "loose" behavior occurs very slowly. Their estimates suggest that the SDP's objective value only clearly exceeds the true maximum when $n$ exceeds $10,000$. This scale is far beyond the reach of standard interior-point solvers like Mosek for general SDPs, explaining why the asymptotic failure remained hidden in earlier empirical work.
Conclusion
This research serves as a cautionary tale for high-dimensional statistics and optimization. It demonstrates that the efficacy of SDP relaxations in small dimensions can be a poor predictor of their asymptotic performance. For non-negative PCA, the natural SDP relaxation eventually hits a spectral barrier, certifying bounds no better than those obtained by ignoring the non-negativity constraint entirely. Future work remains to determine if higher-order Sum-of-Squares (SoS) relaxations can break this barrier, though current evidence suggests the computational wall may be insurmountable for all efficient algorithms.
Summary updated