The sharp SAT/UNSAT phase transition in random ellipsoid fitting

The paper proves the sharp SAT/UNSAT phase transition conjecture for the random ellipsoid fitting problem, as conjectured by Saunderson, Parrilo, and Willsky.

Problem Setup:

The paper considers independent standard Gaussian vectors x 1,, x n about N(0, I d) in R d. An ellipsoid fit is a positive semidefinite matrix S 0 such that x i S x i = d for all i, meaning all points lie on the boundary of the centered ellipsoid x: x S x = d. The feasibility of this semidefinite program is denoted by p(n,d).

Main Result (Theorem 1.2):

The paper proves the sharp transition at n about d 2/4:

• (Satisfiable phase): If d to infinity n/d squared < 1/4, then p(n,d) to 1.

• (Unsatisfiable phase): If d to infinity n/d squared > 1/4, then p(n,d) to 0.

Stronger Existence Result (Theorem 1.3):

Below the threshold, the proof produces a well-conditioned fit: for every alpha* < 1/4, there exist constants 0 < lambda- lambda+ < infinity such that if n/d squared alpha*, then with probability tending to one, there exists an ellipsoid fit S with lambda- I S lambda+ I and Tr(S) = d.

Proof Strategy Overview:

The proof builds on the Gaussian-equivalence framework of Bandeira and Maillard [BM25], closing two gaps: exact fitting (not approximate) and removing the operator-norm constraint.

• Satisfiable side: The proof works directly in the dual problem. It strengthens the feasibility problem by imposing a spectral box constraint and shows that the minimum over the dual unit sphere is bounded away from zero. The key new ingredients are:

• A head-tail decomposition of the dual vector y into a sparse head (at most C 0 d d heavy coordinates) and a low-influence tail.

• Exact correction of the sparse head constraints using the inverse Gram matrix of the second-order chaos, whose singular values are of order d (via the feature-edge result of Kogan, Nandy, and Huang [KNH25]).

• A Gaussian comparison principle (second-chaos Lindeberg principle) for the low-influence tail, which transfers the Gordon margin from Gaussian rows to quadratic chaos rows.

• Unsatisfiable side: The proof shows the empirical risk is uniformly bounded away from zero over all admissible S. The key idea is to split a candidate S into a low-rank spectral head H (eigenvalues exceeding d-1/4) and a diffuse bulk B (Schatten-3 norm bounded by d-1/4). The proof then:

• Conditions on the head variables and Gaussianizes the bulk conditionally.

• Uses a projected Gordon escape argument on the bulk.

• Applies a free-entropy interpolation principle to compare the original model with the hybrid Gaussian model.

Key Technical Contributions:

1. Gaussian width of the PSD cone (Lemma 2.1): The statistical dimension is delta(S d+) = d(d+1)/4, giving the threshold d 2/4.

2. Feature-edge bound (Proposition 2.8): The quadratic feature map Q y satisfies c K p squared I n Q y Q y* C K p squared I n with high probability for n/p squared in K (0, 1/2).

3. Uniform head-section width (Proposition 3.3): Solving any sparse collection of head equations exactly preserves almost all Gaussian width of the bounded-condition cone.

4. Uniform low-influence tail margin (Proposition 3.4): A positive margin for every normalized tail direction with low individual coordinates.

5. Second-chaos Lindeberg principle (Lemma 3.9): Bounds the difference between expectations under quadratic chaos and Gaussian rows by C M 3(F)/sqrt d.

6. Bulk universality with translated losses (Proposition 4.3): The minimum empirical risk under ellipsoid bulk data matches that under Gaussian bulk data, uniformly over arbitrary deterministic head contributions.

7. Hybrid model risk gap (Proposition 4.4): The empirical risk in the hybrid model is bounded away from zero with high probability.

Threshold Mechanism:

The sharp constant 1/4 enters through the comparison of the Gaussian width of the PSD cone (w(S d+ S F) about d/2) with the expected norm of a Gaussian vector (Eg n 2 about sqrt n), giving the critical scale n = d 2/4. The degree-two feature map remains well-conditioned up to n/d squared < 1/2, so the threshold is governed solely by the statistical dimension of the PSD cone.

Related Results:

• The paper proves Corollary 1.4, establishing the threshold for balanced positive definite combinations of random rank-one matrices.

• The proof yields a condition number bound cond(S) = O((1/4 - alpha)-2) as alpha 1/4 (Remark 3.6).

• The replica analysis of Maillard and Kunisky [MK24] predicts the same threshold and a limiting spectral distribution, which the paper's existence result supports but does not characterize.

Improvements to AI Systems:

1. Sharp Phase-Transition Prediction for Constrained Optimization:

The theorem provides a precise, provable threshold (n = d 2/4) for feasibility in high-dimensional quadratic constraints. An AI system can use this to automatically detect when a semidefinite program (SDP) with random quadratic constraints is likely solvable or not, without running expensive solvers. This enables early termination or alternative algorithm selection in optimization pipelines.

2. Conditioned Spectral Bounds for Robust Fitting:

Theorem 1.3 guarantees a well-conditioned solution (lambda- I S lambda+ I) below the threshold. An AI system can exploit this to design regularized solvers that enforce spectral box constraints, improving numerical stability and convergence speed in high-dimensional ellipsoid fitting, subspace recovery, or covariance estimation tasks.

3. Gaussian-Equivalence Transfer for Non-Linear Feature Maps:

The second-chaos Lindeberg principle (Lemma 3.9) allows replacing quadratic chaos rows with Gaussian rows while preserving margin behavior. An AI system can apply this to accelerate training on quadratic feature maps (e.g., kernel methods, polynomial networks) by substituting Gaussian surrogates for complexity analysis, yielding faster hyperparameter tuning and tighter generalization bounds.

4. Head-Tail Decomposition for Sparse High-Dimensional Data:

The head-tail decomposition (sparse head + low-influence tail) offers a generic strategy for handling high-dimensional data with few dominant coordinates. An AI system can use this to compress feature spaces, identify critical dimensions, and allocate computational resources adaptively—improving efficiency in streaming or distributed learning where memory is limited.

5. Free-Entropy Interpolation for Model Comparison:

The bulk universality principle (Proposition 4.3) enables comparing original data with hybrid Gaussian models uniformly over deterministic perturbations. An AI system can leverage this to validate robustness of learned models under distribution shifts, or to generate synthetic data that preserves optimization landscapes—useful for data augmentation and adversarial robustness testing.

6. Statistical Dimension as a Complexity Measure:

The Gaussian width of the PSD cone (d(d+1)/4) serves as a sharp complexity metric. An AI system can compute this for arbitrary constraint sets to predict sample complexity in learning problems (e.g., matrix completion, phase retrieval), enabling automatic selection of regularization strength or data collection requirements.

7. Provable Condition Number Control Near Threshold:

The bound cond(S) = O((1/4 - alpha)-2) gives a quantitative trade-off between sample size and solution stability. An AI system can use this to tune the number of samples n relative to dimension d to achieve a desired numerical precision, avoiding ill-conditioned solutions in real-time decision-making systems.

8. Exact Feasibility Certification for SDP Relaxations:

The proof’s dual-side approach (minimizing over dual unit sphere) provides a certificate of infeasibility or feasibility. An AI system can integrate this as a verification tool for neural network robustness (e.g., certifying that no adversarial ellipsoid contains all data points), improving safety in autonomous systems.

What the Improved AI System Can Do:

• Automatically determine if a random quadratic constraint problem is solvable before solving, saving compute.

• Generate well-conditioned solutions with guaranteed spectral bounds for high-dimensional fitting.

• Accelerate training on polynomial/kernel features via Gaussian surrogates with provable error bounds.

• Compress high-dimensional data by identifying sparse heads, enabling memory-efficient learning.

• Certify robustness of models against distribution shifts using hybrid model comparisons.

• Predict sample complexity for new tasks using Gaussian width calculations.

• Maintain numerical stability near critical sample sizes, preventing solver failures.

• Provide formal feasibility certificates for safety-critical optimization problems.