Exact threshold for approximate ellipsoid fitting of random points

Understand

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 show a universality property for the minimal fitting error achievable by ellipsoids: we show that, to leading order, it coincides with the minimal error in a so-called &#34;Gaussian equivalent&#34; problem, for which the satisfiability transition can be rigorously analyzed.