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 ζ=−ω .
This paper presents an algorithm for detecting and fitting multiple ellipsoids in 2D, 3D and higher-dimensional data. The representation is based on tangents to the ellipsoid together with their contact points, rather than on points alone. A tangent contributes d independent equations where a point contributes one, so each hypothesis needs fewer samples, which in turn reduces the number of iterations required to recover every ellipsoid. The problem is posed as sets of linear equations whose solutions -- the ellipsoid parameters -- are recovered robustly by clustering in parameter space. The algorithm works in all dimensions and outperforms the state of the art in 2D. The approach applies in general to the robust solution of linear equations, and so has utility beyond ellipsoid fitting.
Efrat Dahan, Michael Werman
School of Computer Science, The Hebrew University of Jerusalem, Israel
The John ellipsoid of a symmetric polytope P={x∈Rd:∥Ax∥∞≤1}, A∈Rn×d, is computed by a long line of leverage-score algorithms, from Cohen, Cousins, Lee and Yang (COLT 2019) to its successors [WY24, CLS+25], all reaching a (1+ε)-approximation in Θ(ε−1log(n/d)) iterations. We separate this complexity into three costs the modern line conflates (certification, identification, and accuracy) and locate the historical ε−1 in the first alone. In the equivalent D-optimal-design form minp∈Δn−logdet(∑ipiaiai⊤), the leverage-score oracle is exactly the first-order oracle and the (1+ε)-John guarantee the Frank-Wolfe gap g(p)≤εd; through this dictionary the costs come apart. The ε−1 is a certification artifact: the uniform average of the iterates, the certificate used throughout the line, has gap exactly Θ(1/T), however cheap each iteration is made. Pointed instead at the last iterate the same oracle is fast: a warm-started accelerated method reaches the guarantee in C(A)+O(κlog(1/ε)) queries after an ε-independent setup C(A), and once the optimal face is identified the facial problem is an unconstrained self-concordant minimization whose Hessian the oracle recovers exactly, so damped Newton needs only O(loglog(1/ε)) steps, for a total of C(A)+O(d2loglog(1/ε)) queries. The accuracy dependence is thus doubly logarithmic after an ε-independent, condition-dependent setup; the open problem is the remaining identification cost (a condition-free bound on reaching the optimal face) and lower bounds. Accuracy is not the obstruction.
Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2
University of New South Wales · University of California, Berkeley · University of Sydney
Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is 1+w(A)2, where w(A) is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension d, as β↓0, the sharp worst-case sample complexity is Θ(β−1[dlog(1/β)+log(1/δ)]). The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with O(1+log(1/δ)) samples, whereas an isotropic heavy-tailed design fails pathwise for n≲p/logp. Gaussian smoothing yields an everywhere-positive C∞ density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.
Shi Fu, Huibo Xu, Qixin Zhang +1
Generative AI Lab, College of Computing and Data Science, Nanyang Technological University, Singapore