Exact threshold for approximate ellipsoid fitting of random points
Afonso S. Bandeira, Antoine Maillard · Electronic Journal of Probability · 2025
We consider the problem (P) of exactly fitting an ellipsoid (centered at 0) to n standard Gaussian random vectors in Rd, as n,d→∞ with n∕d2→α>0. This problem is conjectured to undergo a sharp transition: with high probability, (P) has a solution if α1∕4. So far, only a trivial bound α>1∕2 is known to imply the absence of solutions, while the sharpest results on the positive side assume α≤η (for η>0 a small constant) to prove that (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 “Gaussian equivalent” problem, for which the satisfiability transition can be rigorously analyzed. Our main results follow from this finding, and they are twofold. On the positive side, we prove that if α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→∞ (and in particular there does not exist any ellipsoid fit whose shortest axis length is bounded away from 0 as d→∞). To the best of our knowledge, our work is the first rigorous result characterizing the expected phase transition in ellipsoid fitting at α=1∕4. In a companion non-rigorous work, the second author and D. Kunisky give a general analysis of ellipsoid fitting using the replica method of statistical physics, which inspired the present work.