Misiakiewicz & Wen prove sharp ellipsoid fitting phase transition at n ~ d²/4

Theodor Misiakiewicz and Garrett Wen have proven a long-standing conjecture about when random points can be perfectly enclosed by an ellipsoid. The problem: given n independent standard Gaussian vectors in d dimensions, does there exist a positive semidefinite matrix S such that every point lies on the boundary of the ellipsoid {x : xᵀSx = d}? Saunderson, Parrilo, and Willsky conjectured in 2012 that this semidefinite feasibility problem undergoes a sharp phase transition at n ~ d²/4. The new proof, posted on arXiv (2608.10184), confirms this exactly.

On the satisfiable side (n/d² < 1/4), the authors show an ellipsoid fit exists with high probability, and crucially, you can choose S with eigenvalues bounded in a fixed interval. On the unsatisfiable side (n/d² > 1/4), no fit exists even without spectral restrictions. The proof extends the Gaussian-equivalence framework of Bandeira and Maillard, introducing a head-tail decomposition of the dual vector and a Gaussian comparison principle for the low-influence tail. For the unsatisfiable case, they split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, then apply a projected Gordon escape argument. The threshold is governed by the statistical dimension d(d+1)/4 of the positive semidefinite cone.