Ellipsoid Geometry Controls When Factor Analysis Beats PCA in High Dimensions

When the noise on each measured variable has its own variance, the top principal components of the covariance matrix do not point along the true low-dimensional signal. This failure persists even with infinite data, and in high dimensions sampling noise adds a second, separate failure. The classical remedy is factor analysis: split the covariance into a diagonal part (one noise variance per variable) plus a low-rank part (the shared signal). One convex way to do the split is minimum-trace factor analysis, a semidefinite program that finds the diagonal-plus-low-rank split whose low-rank part has the smallest trace. A 2012 result shows that this split recovers the true signal subspace exactly when a set of points built from that subspace lies on a common centered ellipsoid. A separate line of recent work has pinned down the sharp threshold at which random points stop fitting on an ellipsoid: roughly a quarter of the dimension squared.

This proposal joins the two results. We claim that the shape of the dual ellipsoid, and not just whether one exists, governs how stable factor analysis is when it is run on a noisy high-dimensional sample covariance. The prediction is that the ellipsoid's axes spread apart as the sharp threshold approaches, and that this spread multiplies the sampling error. The clean geometric threshold should therefore move inward by an amount that depends on the ratio of variables to samples. Mapping this joint phase diagram tells a practitioner, for a given number of variables, samples and factors, whether factor analysis is worth running instead of PCA.

Why the obvious combination is a dead end

The tempting question at this intersection is the one listed as an open gap: does the ellipsoid-fitting threshold $\alpha_c = 1/4$ shift when the points come from a spiked covariance $\Sigma = I + \theta vv^T$ instead of an isotropic Gaussian? We think the answer is trivially no.

Write $x_i = \Sigma^{1/2} z_i$ with $z_i$ isotropic. Then $x_i^T A x_i = 1$ holds exactly when $z_i^T B z_i = 1$ with $B = \Sigma^{1/2} A \Sigma^{1/2}$, and $B$ is positive definite exactly when $A$ is. So whether an ellipsoid exists is invariant under any invertible linear map of the data. For any fixed-strength spike, the threshold is the isotropic one. Only the axes are distorted, by the known factor $\Sigma^{-1/2}$. This also rules out the idea that the BBP transition (the point below which the top sample eigenvector carries no information about the spike) corresponds to an ellipsoid transition on the raw data points. The spike is invisible to ellipsoid existence.

Structure can move the geometric threshold only if it enters the constraint points themselves, not the covariance of the data. Saunderson et al.'s factor-analysis equivalence is where this happens: there the points are rows of a basis for the complement of the signal subspace.

Core Claim

The prior work plays three roles here. Diagonal and Low-Rank Matrix Decompositions, Correlation Matrices, and Ellipsoid Fitting supplies the bridge. It proves that minimum-trace factor analysis recovers a subspace $U$ exactly if and only if the $p$ rows of an orthonormal basis $W \in \mathbb{R}^{p \times k}$ of $U^\perp$ (with $k = p - r$ for $r$ factors) lie on a common centered ellipsoid. It also gives a sufficient coherence condition $\mu(U) < 1/2$, but it does not treat sampling noise or the large-dimension limit.

Exact threshold for approximate ellipsoid fitting of random points supplies the method. It uses Gaussian interpolation and Gordon's min-max inequality to prove the $\alpha_c = 1/4$ threshold for approximate fitting. Below the threshold the fitting ellipsoid has axes bounded above and below; above it the shortest axis must collapse. Fitting an ellipsoid to random points: predictions using the replica method predicts the threshold and the growing eccentricity of the ellipsoid as the threshold approaches. The rows of $W$ for a random $U$ behave approximately like Gaussian points in $\mathbb{R}^k$, which gives a population-level prediction: exact recovery of $r$ random factors in $p$ variables holds when $p < k^2/4$, that is, when $p - r \gtrsim 2\sqrt{p}$.

Our contribution is the finite-sample version. Let $Y = WAW^T$ be the dual certificate, where $Y$ is a correlation matrix with $U$ in its nullspace and $A$ is the fitting ellipsoid. When the sample covariance $\hat\Sigma$ replaces $\Sigma$, standard perturbation arguments for semidefinite programs say the error scales like the perturbation size divided by the certificate's margin. We hypothesize the following relation for the subspace error of noisy minimum-trace factor analysis:

$$\|\sin\Theta(\hat U, U)\|_F^2 \;\lesssim\; \kappa(A_\star)^2 \,\frac{p}{n},$$

Here $\hat U$ is the estimated subspace, $\sin\Theta$ collects the sines of the principal angles between $\hat U$ and $U$, and $p/n$ is the squared operator-norm size of $\hat\Sigma - \Sigma$ in the proportional regime. The factor $\kappa(A_\star)$ is the ratio of the longest to the shortest axis of the best-conditioned fitting ellipsoid. Because $\kappa$ diverges as $k^2/p \to 4$, the usable region shrinks from the noiseless threshold. The predicted boundary sits where $\kappa(A_\star)^2 p/n$ becomes order one. It moves with $\gamma = p/n$, and it lies on a different axis of the phase diagram from the BBP transition. That is the testable, new content.

Research Program

The theory has two parts. The first uses the Gaussian-equivalence and Gordon machinery of Bandeira and Maillard to compute the limiting distribution of axis lengths of the best-conditioned fitting ellipsoid as a function of $\alpha = p/k^2 < 1/4$. We would extend their bounded-axis statement to an explicit curve $\kappa(\alpha)$, using the replica prediction as a guide. The second turns this into a stability bound for noisy minimum-trace factor analysis. The estimator is $\min \mathrm{tr}(L) + \tfrac{\lambda}{2}\|\hat\Sigma - D - L\|_F^2$ over diagonal $D \succeq 0$ and $L \succeq 0$. The bound would run through the dual certificate, in the spirit of the Gordon-style escape arguments that Phase transitions for the existence of unregularized M-estimators in single index models uses for a vector-valued cone problem. Our setting is a matrix-valued problem with rank-one constraints, which that paper does not treat.

The second strand addresses the open question of structured constraints. Sparse or coherent factor loadings make the rows of $W$ anisotropic and unequal in norm. Unlike a covariance spike, this changes the threshold. This is where the tension between Saunderson's delocalization condition and the localization assumed in sparse PCA (Minimax Rates of Estimation for Sparse PCA in High Dimensions) can be settled quantitatively. The coherence condition is only sufficient, so we expect many moderately sparse subspaces with $\mu(U) > 1/2$ to remain recoverable. We would measure exactly where recovery breaks as a function of support size.

Everything is checked numerically at moderate scale. Semidefinite programs with $p$ up to about 600 are feasible with standard first-order solvers, and ellipsoid-fitting instances with $k$ up to about 80 resolve the $\alpha = 1/4$ transition clearly. These are the scales at which Fitting an ellipsoid to a quadratic number of random points and the replica paper make their predictions.

Baselines

The naive reference point is ordinary PCA on $\hat\Sigma$, keeping the top $r$ eigenvectors. This is what practitioners do, and its failure has two parts. It is biased at population level whenever the noise variances differ across variables. It loses the signal entirely below the BBP boundary $1 + \sqrt{\gamma}$, which Sparse PCA: Phase Transitions in the Critical Regime validated in simulations with $n = 10{,}000$ and $p = 5{,}000$. PCA receives the same data and the true $r$. Beating it means lower $\sin\Theta$ error at matched $(p, n, r)$ over a region of the phase diagram that our theory predicts in advance.

The strongest existing subspace estimator in the file is Fantope Projection and Selection (Fantope Projection and Selection). It is a convex relaxation over the convex hull of rank-$r$ projections, solved by ADMM, and it estimates a whole subspace without deflation. It is the most direct competitor because it is also a semidefinite method for multi-dimensional subspaces. However, it assumes no diagonal-plus-low-rank structure. That paper reports that it outperforms two other sparse PCA methods in $\log(\mathrm{MSE})$ at $n = 100$, $p = 200$, $d = 5$, but no reported result found on Lacuna for its numerical $\log(\mathrm{MSE})$ values. We would therefore reproduce that exact configuration and use our reproduced number as the reference. Fantope will be tuned over its $\ell_1$ penalty on a held-out grid, with the same grid size as our $\lambda$. Beating it means lower subspace error under heteroscedastic noise, with no loss under isotropic noise.

For general-covariance sparse settings in the structured strand, we include the Restarted Truncated Power Method from Combinatorial Sparse PCA Beyond the Spiked Identity Model. It is the fastest method in the file with guarantees beyond identity noise. We also include diagonal thresholding, which High-dimensional analysis of semidefinite relaxations for sparse principal components shows needs order $k^2\log(p-k)$ samples against order $k\log(p-k)$ for the semidefinite relaxation.

Two ablations isolate the key ingredients. The first is minimum-trace factor analysis with $D$ constrained to a multiple of the identity, which removes the diagonal freedom that the ellipsoid geometry is about. The second is an "existence-only" predictor that forecasts success purely from whether $k^2/p > 4$, ignoring $\kappa$. If the existence-only predictor matches the full $\kappa$-based predictor in forecasting where recovery fails, the core claim is wrong.

Why not just…?

Why not just study ellipsoid fitting under a spiked covariance, as the gap list suggests? Because ellipsoid existence is invariant under invertible linear maps, as shown above, the threshold cannot move for any non-degenerate spike. We include this as a sanity check: fitting spiked Gaussian points at $\alpha$ near $1/4$ should give a success curve indistinguishable from the isotropic one. The only change should be that the fitted axes are rotated and stretched by $\Sigma^{-1/2}$.

Why not just rely on Saunderson's coherence condition $\mu(U) < 1/2$? It is sufficient, not necessary. Their Proposition 4.6 only guarantees random subspaces of up to about half the ambient dimension, whereas the ellipsoid threshold predicts recovery up to $r \approx p - 2\sqrt{p}$. Coherence also says nothing about sampling noise. Our first experiment directly measures how much of the recoverable region the coherence condition misses.

Why not just estimate the per-variable noise variances, rescale each variable, and run PCA? This is the real threat. Iterating "estimate the diagonal from the residuals, then whiten" is a simple non-convex heuristic for the same decomposition, and it might keep working past the convex threshold. Failure of minimum-trace recovery does not imply the true factors are unidentifiable; it only means the trace objective prefers a different split. We would include iterated whitening as a baseline under the same tuning budget. If it matches or beats noisy minimum-trace factor analysis everywhere, including beyond $k^2/p = 4$, we would recast the contribution as a characterization of where the convex method's guarantee holds, not a method recommendation.

Why not just simulate the semidefinite program on a grid and skip the theory? Simulations at $p \le 600$ cannot distinguish a threshold shift that scales as $\gamma$ from one that scales as $\sqrt{\gamma}$, or from a finite-size effect. The predicted $\kappa(\alpha)$ curve turns the grid into a test with a definite scaling.

Proposed Experiments

The first experiment is the population check. We draw uniformly random $r$-dimensional subspaces $U \subset \mathbb{R}^p$ for $p \in \{100, 200, 400\}$ and solve exact minimum-trace factor analysis on $D + P_U$, with $D$ having random positive diagonal entries. We record the success probability against $k^2/p$. The expected result is that the curves collapse onto a sharp transition at 4. At each solution we record the axis lengths of the dual ellipsoid and compare them with the predicted $\kappa(\alpha)$.

The second experiment is the decisive finite-sample test. We generate $x = \Lambda f + \varepsilon$ with heteroscedastic diagonal noise, at $\gamma = p/n \in \{0.1, 0.5, 1, 2\}$, signal strengths on both sides of the BBP boundary, and $k^2/p$ swept from 6 down to 4. We measure $\|\sin\Theta\|_F^2$ for PCA, Fantope, iterated whitening, both ablations, and noisy minimum-trace factor analysis. The claim survives only if two things hold. First, the measured failure point of minimum-trace factor analysis moves away from $k^2/p = 4$ as $\gamma$ grows, in the direction the $\kappa(\alpha)^2\gamma$ rule predicts. Second, the per-instance error correlates with the measured $\kappa(A_\star)$ beyond what $k^2/p$ alone explains. A flat dependence on $\gamma$, or no added predictive value from $\kappa$, refutes it.

The third experiment covers structured subspaces. We use $s$-sparse loadings and Johnstone's three-peak signal from A Kernel Random Matrix-Based Approach for Sparse PCA. We locate the recovery boundary as a function of $s$ and compare it with the coherence prediction, with Fantope, and with the Restarted Truncated Power Method.

The fourth experiment applies the method to the NYTimes bag-of-words corpus used by Kumar et al., where word frequencies are strongly heteroscedastic. We evaluate subspace stability across bootstrap resamples and topic coherence by normalized pointwise mutual information. No reported result found on Lacuna for NPMI on this dataset, so all methods are run fresh under one protocol. Because the full $20{,}000$-word vocabulary is beyond semidefinite solvers, we restrict to the top 600 words by frequency and run every method on that same restriction.