Abstract
We consider the problem (P) of exactly fitting an ellipsoid (centered at 0) to $n$ standard Gaussian random vectors in $\mathbb{R}^d$, as $n, d \to \infty$ with $n / d^2 \to \alpha > 0$. This problem is conjectured to undergo a sharp transition: with high probability, (P) has a solution if $\alpha < 1/4$, while (P) has no solutions if $\alpha > 1/4$. So far, only a trivial bound $\alpha > 1/2$ is known to imply the absence of solutions, while the sharpest results on the positive side assume $\alpha \leq \eta$ (for $\eta > 0$ a small constant) to prove that (P) is solvable. In this work we study universality between this problem and a so-called "Gaussian equivalent", for which the same transition can be rigorously analyzed. Our main results are twofold. On the positive side, we prove that if $\alpha < 1/4$, there exist an ellipsoid fitting all the points up to a small error, and that the lengths of its principal axes are bounded above and below. On the other hand, for $\alpha > 1/4$, we show that achieving small fitting error is not possible if the length of the ellipsoid's shortest axis does not approach 0 as $d \to \infty$. To the best of our knowledge, our work is the first rigorous result characterizing the expected phase transition in ellipsoid fitting at $\alpha = 1/4$.
Introduction
The random ellipsoid fitting problem is a fundamental challenge in high-dimensional geometry and statistics. Given $n$ random points in $d$-dimensional space, the goal is to determine if a centered ellipsoid exists such that all points lie on its boundary. As the number of points $n$ grows relative to the dimension $d$, the problem is expected to undergo a sharp phase transition. Specifically, for the ratio $\alpha = n/d^2$, it has been conjectured that a solution almost always exists for $\alpha < 1/4$ and almost never exists for $\alpha > 1/4$.
Despite numerical evidence and heuristic support from statistical physics, rigorous mathematical proof of this $1/4$ threshold has remained elusive. Previous research could only establish solvability for very small values of $\alpha$ or impossibility for $\alpha > 1/2$, leaving a significant gap in the theoretical understanding of the problem's landscape.
Methodology
The authors employ a universality argument to bridge the gap between the structured ellipsoid fitting problem and a more tractable "Gaussian equivalent" model. They demonstrate that in the high-dimensional limit, the specific rank-1 structure of the data constraints ($x_\mu x_\mu^\top$) becomes asymptotically equivalent to generic Gaussian noise (GOE matrices).
The proof utilizes two key mathematical frameworks:
- Gaussian Interpolation: A technique from spin glass theory used to show that the system's free entropy is stable during the transformation from structured data to Gaussian noise.
- Gordon’s Min-Max Theorem: A tool from random convex geometry used to calculate the exact statistical dimension of the cone of positive semidefinite matrices, which formally identifies the $1/4$ threshold.
Key Results
This work provides the first rigorous characterization of the phase transition at $\alpha = 1/4$ for approximate ellipsoid fitting:
- Satisfiable Regime ($\alpha < 1/4$): The authors prove that when $n/d^2 < 1/4$, there exists an ellipsoid that fits all points with an average error that vanishes as $d \to \infty$. The resulting ellipsoid is well-behaved, with principal axes that remain bounded.
- Unsatisfiable Regime ($\alpha > 1/4$): Conversely, for $n/d^2 > 1/4$, it is shown that achieving a small fitting error is impossible unless the ellipsoid becomes extremely degenerate, with its shortest axis shrinking toward zero.
Discussion and Limitations
While this research marks a significant milestone, it focuses on approximate fitting (arbitrarily small error) rather than the original exact fitting conjecture (zero error). Closing the gap for exact fitting remains a difficult challenge, as it requires swapping the order of limits for error and dimension. Furthermore, the negative result for $\alpha > 1/4$ currently relies on the assumption that the ellipsoid's spectrum remains bounded. Future work may explore relaxing this assumption and extending these universality results to non-Gaussian data distributions, such as points uniformly distributed on a sphere.
Summary updated