Fitting ellipsoids to random points: the threshold d²/4
Let $x_1, \dots, x_n$ be i.i.d. $\mathcal{N}(0, I_d/d)$ in $\mathbb{R}^d$. An ellipsoid fit is a centred ellipsoid $\{x : x^{\mathsf T} S x = 1\}$, with $S \succeq 0$, passing through all of them. Counting linear equations shows that with high probability no fit exists once $n > \binom{d+1}{2}$; when the post was written this was the best bound in that direction. Fits exist with high probability for $n \le d^2/C$ (Tulsiani and Wu; Hsieh, Kothari, Potechin and Xu; Bandeira, Maillard, Mendelson and Paquette), and Bandeira and Maillard proved the sharp transition at $d^2/4$ for an approximate fitting problem.
Problem. Prove or disprove that for every $\varepsilon > 0$, $$\limsup_{d \to \infty} \frac{n}{d^2} \le \frac{1 - \varepsilon}{4} \implies \lim_{d \to \infty} \mathbb{P}[\exists \mathcal{E} \text{ an ellipsoid fit to } (x_i)_{i=1}^n] = 1,$$ $$\liminf_{d \to \infty} \frac{n}{d^2} \ge \frac{1 + \varepsilon}{4} \implies \lim_{d \to \infty} \mathbb{P}[\exists \mathcal{E} \text{ an ellipsoid fit to } (x_i)_{i=1}^n] = 0.$$
Source: Saunderson, Parrilo and Willsky (Conjecture 2 of their CDC 2013 paper), from a line of work begun by Saunderson, Chandrasekaran, Parrilo and Willsky (2012). Conjecture 6 of Randomstrasse101, in Maillard's “Fitting ellipsoids to random points” (2024); Entry 3 of arXiv:2504.20539.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- PR — Probability
- Secondary
- MG, ST
- Keywords
- ellipsoid fitting, phase transitions, random geometry, Randomstrasse101, semidefinite programming
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2024,
author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2024},
year = {2025},
eprint = {2504.20539},
archivePrefix = {arXiv}
}
@inproceedings{saunderson2013diagonal,
author = {Saunderson, James and Parrilo, Pablo A. and Willsky, Alan S.},
title = {Diagonal and low-rank decompositions and fitting ellipsoids to random points},
booktitle = {52nd IEEE Conference on Decision and Control},
pages = {6031--6036},
year = {2013}
}
@misc{bandeira2023exact,
author = {Bandeira, Afonso S. and Maillard, Antoine},
title = {Exact threshold for approximate ellipsoid fitting of random points},
year = {2023},
eprint = {2310.05787},
archivePrefix = {arXiv}
}
Resolution claims
We establish a sharp phase transition for fitting random vectors by an ellipsoid. The random vectors have independent subgaussian coordinates with mean zero, variance one, and a common fourth moment, and the number of vectors is proportional to the square of the dimension. We identify an explicit satisfiability threshold such that, with high probability, a positive definite ellipsoid passes through …
We resolve the ellipsoid fitting conjecture of Saunderson, Chandrasekaran, Parrilo, and Willsky up to a vanishing factor. Concretely, for $m$ independent Gaussian points in dimension $d$, we show that with high probability, for $m \leq (1-o_d(1)) \cdot d^2/4$, there exists a centered ellipsoid passing through all $m$ points; for $m\geq (1+o_d(1) )\cdot d^2/4$, no such ellipsoid exists. This confirms that …
Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-06 | Open → Solution claimed | The registry's curators | Universality and sharp thresholds for ellipsoid fitting v1 recorded from arXiv:2608.27372v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00062, "Fitting ellipsoids to random points: the threshold d²/4", clopen.solutions.