Exact threshold for approximate ellipsoid fitting of random points

Antoine Maillard, Afonso S. Bandeira

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.

The landscape of rigorous and conjectured results for the ellipsoid fitting problem across different values of $\alpha = n/d^2$.

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:

  1. 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.
  2. 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

Abstract

We consider the problem $(\rm 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, $(\rm P)$ has a solution if $\alpha < 1/4$, while $(\rm 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 $(\rm 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$ (and in particular there does not exist any ellipsoid fit whose shortest axis length is bounded away from $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$. In a companion non-rigorous work, the first author and D. Kunisky give a general analysis of ellipsoid fitting using the replica method of statistical physics, which inspired the present work.
BibTeX
@inproceedings{maillard2025exact,
  author = {Antoine Maillard and Afonso S. Bandeira},
  title = {{Exact threshold for approximate ellipsoid fitting of random points}},
  booktitle = {Electronic},
  year = {2025},
  doi = {10.1214/25-ejp1378},
}
Figure