# The sharp SAT/UNSAT phase transition in random ellipsoid fitting

arXiv: https://arxiv.org/abs/2608.10184 · HTML: https://mlsanity.com/paper/2608.10184/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 10 Aug 2026.

## Builds on (most cited first, 22 of 22)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [The Gaussian equivalence of generative models for learning with shallow neural networks](https://mlsanity.com/paper/2006.14709/) (2020)
- [Universality of empirical risk minimization](https://mlsanity.com/paper/2202.08832/) (2022)
- [Gaussian Universality of Perceptrons with Random Labels](https://mlsanity.com/paper/2205.13303/) (2022)
- [Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimation](https://mlsanity.com/paper/2302.08923/) (2023)
- [Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime](https://mlsanity.com/paper/2403.08160/) (2024)
- [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015)
- [Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications](https://mlsanity.com/paper/2503.14121/) (2025)
- [The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks](https://mlsanity.com/paper/2505.17958/) (2025)
- [When does Gaussian equivalence fail and how to fix it: Non-universal behavior of random features with quadratic scaling](https://mlsanity.com/paper/2512.03325/) (2025)
- [Overcomplete Independent Component Analysis via SDP](https://mlsanity.com/paper/1901.08334/) (2019)
- [Fitting an ellipsoid to random points: predictions using the replica method](https://mlsanity.com/paper/2310.01169/) (2023)
- [Exact threshold for approximate ellipsoid fitting of random points](https://mlsanity.com/paper/2310.05787/) (2023)
- [Universality of max-margin classifiers](https://mlsanity.com/paper/2310.00176/) (2023)
- [Near-optimal fitting of ellipsoids to random points](https://mlsanity.com/paper/2208.09493/) (2022)
- [The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures](https://mlsanity.com/paper/2410.05609/) (2024)
- [A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points](https://mlsanity.com/paper/2212.11221/) (2022)
- [Fitting an ellipsoid to a quadratic number of random points](https://mlsanity.com/paper/2307.01181/) (2023)
- [Ellipsoid Fitting Up to a Constant](https://mlsanity.com/paper/2307.05954/) (2023)
- [Ellipsoid fitting up to constant via empirical covariance estimation](https://mlsanity.com/paper/2307.10941/) (2023)
- [Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization](https://mlsanity.com/paper/2604.03146/) (2026)

## Built on by (most cited first, 1 of 1)

- [Universality and sharp thresholds for ellipsoid fitting](https://mlsanity.com/paper/2608.27372/) (2026)

## Abstract (arXiv)

Let x1,ldots,xn be independent standard Gaussian vectors in ℝd. An ellipsoid fit is a matrix S succeq 0 such that xi^top S xi =d for every i, so that all the points lie on the boundary of the centered ellipsoid  x : x^top S x = d. Saunderson, Parrilo and Willsky conjectured that, as n,d → ∞, this semidefinite feasibility problem undergoes a sharp transition at n ~ d2/4. We prove this conjecture. If lim sup n/d2 = α^* <1/4, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose S with all eigenvalues in a fixed interval [λ_- , λ_+] subset (0,∞) depending only on α^*. Conversely, if lim inf n/d2 > 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.