Universality and sharp thresholds for ellipsoid fitting

1 Introduction

• The ellipsoid fitting problem asks for a positive semidefinite matrix R satisfying x_i^T R x_i = 1 for every data point.Any such matrix is called an ellipsoid fit.Source: §1 · p. 2
• The Gaussian conjecture predicts a sharp feasibility transition near n = d^2/4, where fits exist below the threshold and fail above it.The positive semidefinite constraint halves the dimension-counting threshold near d^2/2.Source: §1 · p. 2

1.1 Main results

• For independent subgaussian coordinates with mean zero, variance one, and common fourth moment κ, the explicit threshold α⋆(κ) depends only on κ when n/d^2 → α.Below α⋆(κ), a well-conditioned exact fit exists with high probability; above it, no positive semidefinite fit exists and the optimal squared fitting error converges to e⋆(α, κ) > 0.Source: §1.1 · p. 3
• The result resolves the Gaussian ellipsoid fitting conjecture and shows that larger fourth moments produce lower thresholds, while the degenerate κ = 1 case is fit by I_d/d for every sample size.The theorem also covers discrete coordinates whose fourth moments range over (1, ∞).Source: §1.1 · pp. 3–4

1.1.1 The Gaussian model and explicit formula

• The Gaussian model reduces the problem to a covariance-matched Gaussian matrix optimization whose isotropic κ = 3 case explains the d^2/4 threshold through the statistical dimension of the positive semidefinite cone.For general κ, a convex Gaussian min-max theorem yields the asymptotic threshold and error formulas.Source: §1.1.1 · pp. 5–6
• For κ = 3, the explicit formula gives α⋆(3) = 1/4, while α⋆(κ) approaches 1/2 as κ decreases to 1 and the phase transition is continuous but second order.The limiting optimal squared fitting error is identified by e⋆(α, κ), which is noted as new.Source: §1.1.1 · p. 7

1.1.2 Universality and exact fitting

• Universality transfers the asymptotic optimal squared fitting error beyond independent coordinates to centered, identity-covariance vectors satisfying approximate tensorization of variance and uniformly bounded eighth moments.This result applies when n/d^2 → α and includes weakly dependent measures with a dimension-free spectral-gap-type condition.Source: §1.1.2 · pp. 7–8
• Existing interpolation-based universality arguments do not cover squared loss or the full trace-normalized positive semidefinite domain because near-minimizers may contain candidate-dependent spectral spikes.Controlling spiked and nonspiked parts therefore requires a more involved comparison than localization to a fixed Gaussianity domain.Source: §1.1.2 · p. 8
• Theorem 1.7 establishes ΓX universality without no-spike restrictions or coordinate independence via a Lindeberg replacement of Wi by Gi.For squared loss, matching first and second moments cancel the second-order expansion terms; a self-concordant barrier stabilizes the constrained optimization and supplies derivative bounds.Source: §1.1.2 · pp. 8–9
• Exact fitting is more delicate than approximate fitting: isotropy, uniform subgaussianity, and covariance matching alone do not prevent failure caused by exceptional constraints.In the example given, P(x = 0) = 2/(d + 2), so n ≍ d^2 samples contain a zero vector with probability tending to one, ruling out any ellipsoid fit.Source: §1.1.2 · p. 9
• Theorem 1.9 provides uniform matrix-valued interpolation for i.i.d. vectors with independent coordinates when n/d^2 → α ∈ (0, 1/2), enabling approximate fits to become exact.The correction is controlled by vector anti-concentration, preserves positive definiteness after rescaling, and can be viewed as a minimum-norm interpolation result.Source: §1.1.2 · p. 9

1.2 Further related literature

• The paper connects its methods to universality of ERM, least-singular-value and small-ball techniques in random matrix theory, and self-concordant barriers in convex optimization.The interpolation proof uses nuclear-norm lower bounds and compressible/incompressible decompositions, while the universality proof uses a fixed log-determinant barrier during sequential replacements.Source: §1.2 · p. 10
• Viewing ellipsoid fitting as a continuous random CSP, Theorem 1.2 identifies a SAT–UNSAT threshold, with the SAT proof relying on anti-concentration rather than the second moment method.Two concurrent works independently establish the Gaussian threshold d^2/4, while this paper additionally studies universality beyond Gaussian data and optimal squared fitting loss.Source: §1.2 · pp. 10–11

2 Proof overview

• The proof establishes the main theorems through a Gaussian proposition based on the convex Gaussian min–max theorem and separate SAT/UNSAT arguments.Instances are called SAT when an ellipsoid fit exists and UNSAT otherwise.Source: §2 · p. 11

2.1.1 The approximate fit

• Below α < α⋆(κ), a well-conditioned approximate fit has vanishing normalized residual and controlled ℓ∞ residual, enabling later exactification.The approximate matrix satisfies mI_d ⪯ R̂_d ⪯ MI_d with constants depending on α, κ, and K_x.Source: §2.1.1 · pp. 11–12

2.1.2 Small-residual interpolation

• Exactification interpolates the data-dependent residual uniformly: a correction Δ with A_XΔ = ρ̂ and ||Δ||_op = o(1) preserves positive definiteness and yields an exact fit.The required uniform estimate applies to residuals with sufficiently small ℓ2 and ℓ∞ norms, rather than only fixed deterministic residuals.Source: §2.1.2 · pp. 12, 16
• Theorem 2.3 handles the uniformity challenge by decomposing every dual vector into a sparse head and light tail throughout α < 1/2.The proof uses finite nets and exponentially small failure probabilities to overcome their entropy as α approaches 1/2.Source: §2.1.2 · p. 14
• Proposition 2.4 supplies anti-concentration without density or arithmetic assumptions, including for discrete variables, at the cost of requiring η ≳ max_i ||w_i||_2.Its proof uses Fourier analysis and the Brascamp–Lieb inequality, while the scale restriction is unavoidable for lattice-valued variables.Source: §2.1.2 · pp. 14–15

2.2 UNSAT: universality of constrained least squares

• The UNSAT proof uses a Lindeberg argument to establish universality of constrained least squares for quadratic features under regularity conditions.The framework introduces ridge regularization, then verifies concentration-type conditions for the quadratic feature array.Source: §2.2 · pp. 16–17

2.2.2 Removing the barrier and ridge regularization

• The log-determinant barrier has parameter O(d), yielding a vanishing universality error (log d/d)^(1/3) when n ≍ d^2.A generic O(d^2) barrier parameter would not suffice, so the sharper matrix-domain scaling is essential.Source: §2.2.1 · p. 18, §2.2.2 · p. 21

2.2.1 Universality from self-concordant barriers

• Theorem 2.9 compares barrier- and ridge-regularized constrained least-squares values for regular features and matching Gaussian features.The comparison uses second-order feature replacement and controls errors from approximation and quadratic fluctuations.Source: §2.2.1 · p. 19

2.2.2 Removing the barrier and ridge regularization

• The barrier-removal gap satisfies 0 ≤ ΦZ(D, B; β) − ΦZ(D; β) ≤ εFZ(θref, bref; β) + γB(θref) + γϑ log(1/ε), while ridge removal compares regular and Gaussian features when n/d2 → α ∈ (0, ∞) and τd ≤ C0(log d)−3.Source: §2.2.2 · pp. 20–21

2.2 UNSAT: universality of constrained least squares

• If α > α⋆(κ), the limiting optimal fitting error satisfies e⋆(α, κ) > 0, so the probability of an ellipsoid fit tends to zero.The argument transfers the Gaussian limit through Corollary 2.13 and uses that an ellipsoid fit would require zero fitting error.Source: §2.2.2 · p. 22

2.2.3 Lindeberg argument: proof of Theorem 2.9

• The Lindeberg proof replaces features one at a time, expressing each replacement through an insertion-cost difference and a second-order expansion around the leave-one-out optimizer.Ridge regularization makes the leave-one-out Hessian positive definite, enabling inversion in the Taylor control.Source: §2.2.3 · pp. 22–23
• Leave-one-out analysis yields a uniform quadratic approximation for each replacement, using condition (F1) and self-concordance to control the remainder and ensure feasibility.The quadratic problem may not initially be feasible, so self-concordance is essential for both feasibility and remainder control.Source: §2.2.3 · pp. 24–25
• Conditional fluctuations of the leave-one-out denominator are controlled under condition (F2), with covariance matching giving the required comparison between the original and Gaussian replacements.The resulting estimates compare ri(Zi)^2/[2(n+ℓi(Zi))] for Zi = Wi and Zi = Gi.Source: §2.2.3 · p. 25
• Summing the replacement differences over i proves the expectation comparison between the W and G optimized values.The telescoping identity writes the total difference as the sum of E[Φi − Φi−1].Source: §2.2.3 · p. 26
• The variance bound follows by resampling one vector at a time, applying the Efron–Stein inequality, and reusing the leave-one-out estimates.The original and resampled problems share the same conditional leave-one-out objective, allowing the preceding bounds to apply unchanged.Source: §2.2.3 · p. 26
• Combining the expectation and variance bounds with Chebyshev’s inequality completes the proof of the stated probabilistic conclusion.The final step explicitly combines equations (25) and (26) to obtain (27).Source: §2.2.3 · p. 26

3.1 A priori estimates

• Under n ≤ C0d^2, Proposition 3.1 establishes simultaneous high-probability a priori estimates for the data-derived operators, using Hanson–Wright concentration.These estimates support the sparse nuclear norm lower bound in Proposition 3.3 for vectors supported on at most C0d log d coordinates.Source: §3.1 · pp. 27, 29

3.2 Proof of Theorem 2.3

• For n/d^2 → α ∈ (0, 1/2), Proposition 3.4 lower-bounds the light-tail quotient norm uniformly over sparse supports and K-light tails with probability 1 − o(1).Together with Propositions 3.1 and 3.3, this bound implies Theorem 2.3 through a shelling argument.Source: §3.2 · pp. 30–31
• The proof of Proposition 3.4 decomposes coefficient vectors by repeatedly removing their largest coordinates until the remaining tail is K-light or has negligible squared ℓ2 norm.The sparse correction is controlled through the quotient norm bound, allowing the tail contribution to be absorbed into the sparse lower bound.Source: §3.2 · p. 31

3.3 Proof of the Proposition 2.4

• Proposition 2.4 is proved by Fourier-analytic concentration methods: truncated second moments yield interval anti-concentration, while multidimensional extension uses Brascamp–Lieb and Gaussian regularization.The argument follows and its multidimensional extension, with the Brascamp–Lieb inequality stated explicitly as a key ingredient.Source: §3.3 · pp. 32–34
• A smoothed linear combination has uniformly bounded density, providing the anti-concentration input for Proposition 2.4.For independent mean-zero, variance-one coordinates and sufficiently small Gaussian smoothing, Fourier inversion yields ||f_Ys||∞ ≤ C^m.Source: §3.3 · p. 34

3.4 Deterministic light-tail argument

• For a fixed K-light tail, coordinate decoupling, Proposition 2.4, and nuclear-norm covering imply a uniform lower bound on ||L_X^*(h + t)||_* with high probability.The covering lemma gives N(K, ||·||_1,2, γ) ≤ C^(mq) for K = {A: ||A||_* ≤ γd}, enabling the columnwise anti-concentration estimates to be combined.Source: §3.4 · pp. 36–37

3.5 Uniform light-tail lower bound via sequential block revealing

• A single rectangular block closes the uniform argument only for α < 1/4, motivating sequential block revealing for larger α.With L blocks, the exponent becomes D_L = ((1 − 1/L)/2 + o(1))d^2, so sufficiently large L yields the full range α < 1/2.Source: §3.4 · p. 38, §3.5 · pp. 38–39
• Uniformly over K-light tails, the covariance matrix has at most ⌊εp⌋ eigenvalues below an absolute constant, yielding an effective-rank subspace of dimension at least (1 − ε)p.Lemma 3.12 establishes this under independent mean-zero, variance-one, subgaussian coordinates with common fourth moment and n ≤ C0d^2; the resulting subspace satisfies PVΣtPV ⪰ μPV.Source: §3.5 · pp. 39–40
• The sequential block argument controls the conditional small-ball probability by exploiting conditional independence, covariance lower bounds, and an ℓ1-cover of the projected columns.After identifying the relevant subspace with R^m, the covering number is at most C^{m q_ℓ}, and Proposition 2.4 bounds each supremum when γ is sufficiently large relative to K^−1/2.Source: §3.5 · pp. 41–42
• With probability 1−o(1), the block-revealing construction simultaneously gives m_t,ℓ≥(1−ε)p_ℓ for every admissible I and light tail t.The bound follows by applying Lemma 3.12 and Corollary 3.13 with p_ℓ proportional to d and n/d^2→α.Source: §3.5 · pp. 41, 43
• A net over admissible head and tail vectors transfers the fixed-pair estimate to all pairs, with exp(o(d^2)) total net complexity.The admissible class has supp h of size O(d log d), while the tail and head nets satisfy the stated volume bounds.Source: §3.5 · pp. 43–44
• Choosing γ sufficiently small and K sufficiently large makes the bad event E_bad have probability o(1), completing the uniform lower-bound proof.The exponent in the union bound tends to −∞ as γ↓0, while K is chosen so that 2γ≥CK^−1/2.Source: §3.5 · pp. 43–44

4.1 Leave-one-out localization and feature comparison

• Leave-one-out analysis localizes the optimizer and compares exact updates with their unconstrained quadratic approximations for the original and Gaussian features.The proof uses Hessian block decompositions, self-concordant barriers, and conditional independence of the data features.Source: §4.1 · pp. 45, 47

4.2 Quadratic-feature regularity and approximate fitting

• Approximate tensorization of variance yields Lp moment estimates that establish the quadratic-feature regularity conditions used in the universality argument.The resulting estimates cover p = 2, 4, 8 and control both linear and centered quadratic features.Source: §4.2 · pp. 48, 50
• The regularity conditions apply to product subgaussian data, giving a dimension-free regularity constant and τ_d = O(d^-1/2).This follows from independent coordinates, approximate tensorization, covariance matching, and a uniform eighth-moment bound.Source: §4.2 · p. 50
• A Gaussian positive semidefinite fit lies in the bounded spectral class and has zero empirical loss, providing the approximate fit used in the SAT argument.The construction uses a Gaussian matrix fit R_G and bounds its operator norm when n ≍ d^2.Source: §4.2 · pp. 50–51

4.3 Removal of ridge regularization

• Rademacher complexity and matrix concentration control the effect of removing ridge regularization, with a bound of at most C d(log d)^3/4.The argument uses covariance matching, condition (F2), and matrix Bernstein concentration.Source: §4.3 · p. 52
• The function classes have a dimension-independent small-ball probability, with Q_FZ,A(1/2) ≥ 9/(16C4) > 0.This follows from unit second moments, uniformly bounded fourth moments, and the Paley–Zygmund inequality.Source: §4.3 · p. 53
• Small-ball estimates then give a uniform lower bound on the squared loss with probability at least 1 − 2 exp(−q0^2 n/8), simultaneously for Z = W and Z = G with probability tending to one.The argument chooses A sufficiently large and d sufficiently large so the complexity and sample-size errors are dominated by the small-ball term.Source: §4.3 · pp. 53–54
• The unregularized affine-loss minimizers remain in a bounded-loss region with probability tending to one for both W and G.A uniform fourth-moment bound and Chebyshev’s inequality control the empirical trace term, while comparison with (I_d, 0) supplies the needed upper bound.Source: §4.3 · p. 54
• For both Z = W and Z = G, and every β > 0, the regularized infimum is bounded by Cβ log d, while the reverse inequality follows from nonnegative ridge terms.Continuity allows the infimum to be tested at the unregularized minimizer, completing the removal of ridge regularization.Source: §4.3 · p. 54

5 The Gaussian feature model

• The Gaussian proof uses Gaussian processes, convex geometry, the Gaussian min–max theorem, and the GOE semicircle law to establish the exact-fitting results.A well-conditioned fit in the Gaussian analog is constructed in the final subsection for the exact-fitting regime.Source: §5 · p. 54

5.1 CGMT reduction to a shifted cone projection

• CGMT converts the Gaussian primary optimization into an easier auxiliary optimization, represented as the size of a shifted GOE projection onto the rescaled positive-semidefinite cone.The Gaussian matrix representation follows from projecting i.i.d. Gaussian features onto the orthogonal complement of the all-ones direction.Source: §5.1 · pp. 56–57

5.2 Analysis of the scalar variational problem

• The scalar variational problem has a unique solution, with χ_κ(ζ) nondecreasing and α⋆(κ) ranging from 1/2 as κ→1 to 0 as κ→∞.The analysis also gives the duality relation linking κ and κ∨ through the scalar profiles.Source: §5.2 · pp. 59–60
• At κ = 3, the projected spectral law clips the semicircle spectrum at a cutoff, maps the retained portion to positive eigenvalues, and places the clipped mass at zero.At the critical point α⋆(3) = 1/4, the law has an atom of mass 1/2 at zero and the rescaled positive half of the semicircle law.Source: §5.2 · p. 61
• The limiting squared loss has a continuous first derivative but a discontinuous second derivative at the critical threshold, indicating a second-order phase transition.The signed auxiliary optimizer continues algebraically into the SAT phase but may be ill-conditioned, so the exact proof uses a separate well-conditioned fit.Source: §5.2 · p. 62

5.3 Evaluation of the shifted projection

• The shifted cone projection converges for every fixed κ > 1 and ζ ∈ R to the scalar limit χκ(ζ).For κ ≥ 3, the spectral comparison value is expressed using the solution of ωd + ζ = cκmd(ωd), with the optimizer diagonal in the GOE eigenbasis; semicircle convergence extends the result to all κ > 1.Source: §5.3 · p. 63
• The signed auxiliary value converges at the crossing ζ∗, and CGMT transfers this convergence to the primary Gaussian optimization value Φd.The crossing relation brackets the signed auxiliary value around ζ∗, while the CGMT tail comparisons yield convergence of Φd.Source: §5.3 · p. 65

5.4 Well-conditioned fit

• Below α⋆(κ), an exact fit exists with high probability whose shape matrix satisfies mI_d ⪯ R ⪯ MI_d and Tr R = d.The constants 0 < m < M < ∞ depend only on κ and the distance from α to α⋆(κ).Source: §5.4 · pp. 65–66
• Above α⋆(κ), the limiting optimal squared fitting error is positive, yielding a fixed positive lower bound on the fitting error with high probability.The proof identifies the limit through Proposition 5.16 and uses e⋆(α, κ) > 0 to choose c0 = e⋆(α, κ)/2.Source: §5.4 · p. 66

• It derives an abstract consequence of the universality theorem.Source: A Extra corollaries, obstructions, and… · p. 66
• It identifies several obstructions to exact ellipsoid fitting.Source: A Extra corollaries, obstructions, and… · p. 66
• It reports numerical details that are not used in proving the phase transition.Source: A Extra corollaries, obstructions, and… · p. 66

Geometric interpretation

• Singular PSD fits are cylindrical degenerations: bounded ellipsoids on ker(Q)^⊥ extended freely along ker(Q), unlike genuine positive-definite ellipsoids.Positive definiteness distinguishes the SAT theorem’s genuine ellipsoid from degenerate boundary fits.Source: §A.1 · p. 66

UNSAT dual certificate

• In the UNSAT regime, the positive least-squares energy has an exact dual interpretation as sample reweighting.The identity holds for every deterministic sample X.Source: §A.1 · p. 66
• The dual certificate is strictly positive exactly when some centered reweighting λ ∈ 1^⊥ satisfies the stated certificate condition.This equivalence is the proposition’s characterization of Γ_X > 0.Source: §A.1 · pp. 66–67
• When Γ_X > 0, the normalized optimal residual λ⋆ = AXR⋆/∥AXR⋆∥₂ itself yields a strict positive-definite separating certificate.This conclusion combines the dual identity with Theorem 1.2.Source: §A.1 · p. 67

Proof mechanism

• The proof combines fixed-γ row comparison with barrier removal, using the self-concordance bound and an anchor-based sandwich to control the approximation error.Centering and covariance matching bound the anchor objective, while Chebyshev’s inequality controls its random fluctuation and the deterministic terms contribute at most C∆n.Source: §A.2 · pp. 67–68

General-domain comparison

• For any bounded convex relatively open domain D with a ϑ-self-concordant barrier B, Proposition A.2 compares the W- and Gaussian-feature objectives ΦW(D; β) and ΦG(D; β).The assumptions include a (Kfeat, τ)-regular feature W with covariance operator norm λΣ > 0, its matching centered Gaussian feature G, and fixed anchor (θref, bref).Source: §A.2 · p. 68
• For every t > 0, P{|ΦW(D; β) − ΦG(D; β)| > C∆n + t} ≤ C(1 + β−1)2K2.The constants C and c0 depend only on Kfeat.Source: §A.2 · p. 68

Signed-atom obstruction

• Regular features with τd = Oκ(d−1/2) can still admit no exact fit with high probability when n/d^2 → α > 0.Adding rare copies of ±Id/d to a Gaussian background preserves the target covariance and regular-feature estimates, but forces incompatible row values 1 and −1.Source: §A.3 · p. 69
• The signed-atom construction has normalized residual at least order d−1/2, equivalently energy n−1||AW R||2 at least order d−1.Thus the regularity conditions do not force exact fitting even when their error scale is τd = Oκ(d−1/2).Source: §A.3 · pp. 69–70

Nonatomic geometric obstruction

• A centered ellipsoid intersects a noncontained algebraic curve of degree D in at most 2D points, by projective Bézout’s theorem.The bound also covers multiplicities, complex points, and points at infinity; unbounded curves automatically satisfy the required noncontainment.Source: §A.3 · p. 70

Mixture obstruction

• A mixture with nonatomic curve mass fails exact fitting with high probability whenever npd → ∞ and Dd = o(npd).The curve observations are almost surely distinct, while any fitting ellipsoid can contain at most 2Dd of them.Source: §A.3 · pp. 70–71

Isotropic subgaussian example

• Even isotropy and dimension-free subgaussian linear marginals do not prevent obstruction when substantial probability mass lies on a low-degree algebraic set.A Gaussian–uniform line mixture provides a nonatomic example with these properties.Source: §A.3 · p. 71

A.4 Nuclear-norm minimizers below the SAT threshold

• Nuclear-norm minimizing exact fits have only a small negative spectral part under near-identity empirical covariance and existence of a PSD exact fit.This proves a quantitative approximation to the conjecture that nuclear-norm minimizing exact fits are PSD in the SAT phase.Source: §A.4 · p. 72
• An additional trace constraint upgrades approximate positivity to exact positive semidefiniteness.Source: §A.4 · p. 72
• The proof bounds the optimal nuclear norm using a PSD competitor, controls the trace by averaging interpolation equations, and uses ∥S∥∗−Tr S = 2∥S−∥∗ to control negativity.Source: §A.4 · p. 72

Proof mechanism

• The bounds arise by combining nuclear–operator norm duality with interpolation constraints, yielding control of trace deviation and the negative-part nuclear norm.A PSD competitor bounds the nuclear norm, while d = Tr bS + ⟨bΣ − Id, bS⟩ supplies the trace estimate.Source: Consider the exact nuclear-norm program · p. 72

Below-threshold nuclear minimizers are almost PSD

• Below threshold, the exact nuclear-norm program is feasible with probability tending to one, and all minimizers satisfy uniform near-PSD bounds.These conclusions follow from the SAT theorem and sample-covariance concentration, uniformly over the minimizer set.Source: Consider the exact nuclear-norm program · p. 73

Trace-normalized nuclear minimizers are PSD

• Every trace-normalized nuclear-norm minimizer is positive semidefinite with probability tending to one below the threshold.Rescaling a positive definite feasible point to trace d forces every minimizer’s nuclear norm to equal its trace, eliminating its negative part.Source: Consider the exact nuclear-norm program · p. 73

• For 1 ≤ κ ≤ 3, the experiments use a location mixture of two Gaussians whose fourth moment is κ, with κ = 3 as the Gaussian limit.Source: §A.5 · p. 73
• For κ ≥ 3, they use a scale mixture ξ = AZ calibrated so that Eξ^2 = 1 and Eξ^4 = κ, agreeing with the first family at κ = 3.Source: §A.5 · p. 73
• The study evaluates κ ∈ {1.05, 1.25, 1.5, 2, 3, 5, 7.5, 10, 15, 20, 25, 30} using eight independent trials per value and nested samples.Source: §A.5 · p. 73
• For each trial, binary search estimates the largest feasible n/d^2 using an SDP, declaring feasibility when the certified spectral margin is nonnegative up to tolerance 10^-5.Figure 1 reports each trial's largest feasible n/d^2, its mean, middle 50 percent interval, and the curve α⋆(κ).Source: §A.5 · p. 73