We establish a sharp phase transition for fitting random vectors by an ellipsoid. The random vectors have independent subgaussian coordinates with mean zero, variance one, and a common fourth moment, and the number of vectors is proportional to the square of the dimension. We identify an explicit satisfiability threshold such that, with high probability, a positive definite ellipsoid passes through every data point below the threshold, whereas no positive semidefinite fit exists above it. We also determine the optimal squared fitting error throughout the unsatisfiable regime. In particular, the threshold depends on the coordinate distributions only through their common fourth moment, revealing a fourth moment universality phenomenon. For standard Gaussian data the threshold is 1/4, resolving the ellipsoid fitting conjecture.
Figures & tables
Figure 1: The phase diagram and a numerical experiment in dimension d=40 . The curve is the theoretical threshold α⋆(κ) . For each value of κ , eight independent trials use i.i.d. coordinates drawn from a centered, variance one mixture of two Gaussians with fourth moment κ ; we refer to Appendix A.5 . For each trial, a binary search in the number of samples n (y-axis) estimates the largest sample size for which the SDP maximizing t subject to R−tId⪰0 and xi⊤Rxi=d , i=1,…,n , is feasible with nonnegative optimum.
Figure 2: Squared loss for the d=40 experiment. The setup is the same as Figure 1 , except that for each cell we average the squared loss over three trials. The left panel is empirical and the right panel is the asymptotic formula. The x-axis is the fourth moment κ , the y-axis is n/d2 , and black denotes zero loss.
Figure 3: Sequential blocks for L=5 . At stage ℓ , the shaded rectangle LX,ℓ∗λ uses the previously exposed rows Uℓ=I1∪⋯∪Iℓ−1 and the fresh columns Iℓ .
Figure 4: Spectral interpretation of the CGMT calculation for κ=3 . Panel (a) shows the GOE semicircle law and the cutoff ω=−ζ : the gray region x≤ω is clipped to zero, while x>ω is retained. Panel (b) shows the resulting trace-normalized spectral profiles; the curves are the continuous parts and the spikes are the atoms at zero. In the SAT phase α−<α⋆ , the orange profile is the continuation of the signed CGMT auxiliary optimizer, but our exact fitting proof instead uses the well-conditioned fit constructed in Lemma 5.17 . Panel (c) shows how the level crossings χ3(ζ)=α select the corresponding values of ζ=−ω .