Sharp Phase Transition for Ellipsoid Fitting

Abstract

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 the ellipsoid fitting problem has a sharp phase transition at $d^2/4$.

Disclosure

“cknowledgments We are grateful to Sidhanth Mohanty for bringing the independent, concurrent work to our attention. We also thank Frederic Koehler and Youngtak Sohn for coordinating the preparation of the manuscripts. AI Disclosure We used generative AI tools to help polish the writing. All the conceptual contributions are our own, and we take full responsibility for any errors. We also note that the connection to the prior work of [KNH25] was brought to the attention of one of the author”

PDF page 7

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T05:10:57.582250Z

Structural counts