  We consider the problem $(\rm P)$ of exactly fitting an ellipsoid (centered
at $0$) to $n$ standard Gaussian random vectors in $\mathbb{R}^d$, as $n, d \to
\infty$ with $n / d^2 \to \alpha > 0$. This problem is conjectured to undergo a
sharp transition: with high probability, $(\rm P)$ has a solution if $\alpha <
1/4$, while $(\rm P)$ has no solutions if $\alpha > 1/4$. So far, only a
trivial bound $\alpha > 1/2$ is known to imply the absence of solutions, while
the sharpest results on the positive side assume $\alpha \leq \eta$ (for $\eta
> 0$ a small constant) to prove that $(\rm P)$ is solvable. In this work we
study universality between this problem and a so-called "Gaussian equivalent",
for which the same transition can be rigorously analyzed. Our main results are
twofold. On the positive side, we prove that if $\alpha < 1/4$, there exist an
ellipsoid fitting all the points up to a small error, and that the lengths of
its principal axes are bounded above and below. On the other hand, for $\alpha
> 1/4$, we show that achieving small fitting error is not possible if the
length of the ellipsoid's shortest axis does not approach $0$ as $d \to \infty$
(and in particular there does not exist any ellipsoid fit whose shortest axis
length is bounded away from $0$ as $d \to \infty$). To the best of our
knowledge, our work is the first rigorous result characterizing the expected
phase transition in ellipsoid fitting at $\alpha = 1/4$. In a companion
non-rigorous work, the first author and D. Kunisky give a general analysis of
ellipsoid fitting using the replica method of statistical physics, which
inspired the present work.
