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\le (1-o_d(1))\cdot d^2/4$, there exists a centered ellipsoid passing through all $m$ points; for $m\ge (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$.