# Near-optimal fitting of ellipsoids to random points

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 46 references that are in the map.
- First posted on arXiv 19 Aug 2022.

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

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Optimal Spectral Recovery of a Planted Vector in a Subspace](https://mlsanity.com/paper/2105.15081/) (2021)
- [Strongly Refuting Random CSPs Below the Spectral Threshold](https://mlsanity.com/paper/1605.00058/) (2016)
- [Overcomplete Independent Component Analysis via SDP](https://mlsanity.com/paper/1901.08334/) (2019)
- [Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4](https://mlsanity.com/paper/1911.01411/) (2019)
- [Algorithmic Thresholds for Refuting Random Polynomial Systems](https://mlsanity.com/paper/2110.08677/) (2021)

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

- [A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points](https://mlsanity.com/paper/2212.11221/) (2022)
- [Fitting an ellipsoid to a quadratic number of random points](https://mlsanity.com/paper/2307.01181/) (2023)
- [The sharp SAT/UNSAT phase transition in random ellipsoid fitting](https://mlsanity.com/paper/2608.10184/) (2026)
- [Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise](https://mlsanity.com/paper/2510.08541/) (2025)

## Abstract (arXiv)

Given independent standard Gaussian points v1, ldots, vn in dimension d, for what values of (n, d) does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of the points? This basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. Based on strong numerical evidence, Saunderson, Parrilo, and Willsky [Proc. of Conference on Decision and Control, pp. 6031-6036, 2013] conjecture that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points n increases, with a sharp threshold at n ~ d2/4. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some n = Omega( , d2/polylog(d) ,), improving prior work of Ghosh et al. [Proc. of Symposium on Foundations of Computer Science, pp. 954-965, 2020] that requires n = o(d3/2). Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix and a careful analysis of its Neumann expansion via the theory of graph matrices.