The sharp SAT/UNSAT phase transition in random ellipsoid fitting

Abstract

Let $x_1,\dots ,x_n$ be independent standard Gaussian vectors in ${\mathbb{R}}^d$. An \emph{ellipsoid fit} is a matrix $S⪰0$ such that $x_i^{\top }S{x}_i=d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{x:x^{\top }Sx=d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d\to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n\sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2={\alpha }^{\ast }<1/4$, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose $S$ with all eigenvalues in a fixed interval $[{\lambda }_{-},{\lambda }_{+}]\subset (0,\infty )$ depending only on ${\alpha }^{\ast }$. Conversely, if $\lim \inf n/d^2>1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension $d(d+1)/4$ of the positive semidefinite cone.