# Fitting an ellipsoid to a quadratic number of random points

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 20 references that are in the map.
- First posted on arXiv 3 Jul 2023.

## Builds on (most cited first, 3 of 3)

- [Overcomplete Independent Component Analysis via SDP](https://mlsanity.com/paper/1901.08334/) (2019)
- [Near-optimal fitting of ellipsoids to random points](https://mlsanity.com/paper/2208.09493/) (2022)
- [A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points](https://mlsanity.com/paper/2212.11221/) (2022)

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

- [The sharp SAT/UNSAT phase transition in random ellipsoid fitting](https://mlsanity.com/paper/2608.10184/) (2026)

## Abstract (arXiv)

We consider the problem (P) of fitting n standard Gaussian random vectors in ℝd to the boundary of a centered ellipsoid, as n, d → ∞. This problem is conjectured to have a sharp feasibility transition: for any varepsilon > 0, if n ≤ (1 - varepsilon) d2 / 4 then (P) has a solution with high probability, while (P) has no solutions with high probability if n ≥ (1 + varepsilon) d2 /4. So far, only a trivial bound n ≥ d2 / 2 is known on the negative side, while the best results on the positive side assume n ≤ d2 / polylog(d). In this work, we improve over previous approaches using a key result of Bartl & Mendelson (2022) on the concentration of Gram matrices of random vectors under mild assumptions on their tail behavior. This allows us to give a simple proof that (P) is feasible with high probability when n ≤ d2 / C, for a (possibly large) constant C > 0.