# Ellipsoid fitting up to constant via empirical covariance estimation

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

## Key facts

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

## 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)

The ellipsoid fitting conjecture of Saunderson, Chandrasekaran, Parrilo and Willsky considers the maximum number n random Gaussian points in ℝd, such that with high probability, there exists an origin-symmetric ellipsoid passing through all the points. They conjectured a threshold of n = (1-od(1)) · d2/4, while until recently, known lower bounds on the maximum possible n were of the form d2/(log d)O(1). We give a simple proof based on concentration of sample covariance matrices, that with probability 1 - od(1), it is possible to fit an ellipsoid through d2/C random Gaussian points. Similar results were also obtained in two recent independent works by Hsieh, Kothari, Potechin and Xu [arXiv, July 2023] and by Bandeira, Maillard, Mendelson, and Paquette [arXiv, July 2023].