# Fitting an ellipsoid to random points: predictions using the replica method

arXiv: https://arxiv.org/abs/2310.01169 · HTML: https://mlsanity.com/paper/2310.01169/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2023.

## Built on by (most cited first, 7 of 7)

- [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024)
- [Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime](https://mlsanity.com/paper/2509.24882/) (2025)
- [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025)
- [Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Laws](https://mlsanity.com/paper/2509.24914/) (2025)
- [Bayes optimal learning of attention-indexed models](https://mlsanity.com/paper/2506.01582/) (2025)
- [Factual recall in linear associative memories: sharp asymptotics and mechanistic insights](https://mlsanity.com/paper/2605.10795/) (2026)
- [The sharp SAT/UNSAT phase transition in random ellipsoid fitting](https://mlsanity.com/paper/2608.10184/) (2026)

## Abstract (arXiv)

We consider the problem of fitting a centered ellipsoid to n standard Gaussian random vectors in ℝd, as n, d → ∞ with n/d2 → α > 0. It has been conjectured that this problem is, with high probability, satisfiable (SAT; that is, there exists an ellipsoid passing through all n points) for α < 1/4, and unsatisfiable (UNSAT) for α > 1/4. In this work we give a precise analytical argument, based on the non-rigorous replica method of statistical physics, that indeed predicts a SAT/UNSAT transition at α = 1/4, as well as the shape of a typical fitting ellipsoid in the SAT phase (i.e., the lengths of its principal axes). Besides the replica method, our main tool is the dilute limit of extensive-rank "HCIZ integrals" of random matrix theory. We further study different explicit algorithmic constructions of the matrix characterizing the ellipsoid. In particular, we show that a procedure based on minimizing its nuclear norm yields a solution in the whole SAT phase. Finally, we characterize the SAT/UNSAT transition for ellipsoid fitting of a large class of rotationally-invariant random vectors. Our work suggests mathematically rigorous ways to analyze fitting ellipsoids to random vectors, which is the topic of a companion work.