Source-linked AI summary
Universality and sharp thresholds for ellipsoid fitting
Frederic Koehler, Youngtak Sohn
TL;DR
The paper asks when random vectors can be fit exactly by an ellipsoid and whether a universal sharp threshold persists beyond Gaussian data. It establishes an explicit threshold for independent subgaussian coordinates and shows that its location depends only on the common fourth moment, resolving the Gaussian conjecture.
Problem
The work studies the sharp transition between satisfiable and unsatisfiable ellipsoid fitting for random vectors, extending a Gaussian conjecture to broader distributions.
Method
The paper analyzes independent subgaussian coordinates with mean zero, variance one, and common fourth moment, using the scaling n/d^2 → α and Gaussian min–max methods for the Gaussian case.
Results
An explicit threshold α⋆(κ) depends only on the fourth-moment parameter: below it an ellipsoid fit exists with probability tending to one, while above it no fit exists with probability tending to one.
Takeaways & Limitations
The threshold exhibits fourth-moment universality across the stated subgaussian class, while exact fitting can nevertheless depend strongly on the point distribution.
Takeaways & Limitations
Exact fitting is constrained by distribution-specific obstructions, including zero samples that occur with high probability for some distributions when n is proportional to d^2.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper establishes a sharp ellipsoid-fitting transition for random vectors, with threshold α⋆(κ) determined only by the common fourth moment. Below it, well-conditioned exact fits exist with high probability; above it, no positive semidefinite fit exists and the optimal squared error is positive.
- 1 Introduction: The ellipsoid-fitting problem asks whether a positive semidefinite matrix R can satisfy x_i^T R x_i = 1 for every data point.Any matrix satisfying these constraints is called an ellipsoid fit.
- 1 Introduction: Numerical Gaussian experiments suggested a sharp transition near d^2/4, motivating the Gaussian ellipsoid fitting conjecture.The conjecture concerns random standard Gaussian vectors and feasibility as n scales with d^2.
- 1.1 Main results: The explicit threshold α⋆(κ) depends only on the common fourth moment for independent, mean-zero, variance-one subgaussian coordinates.The asymptotic regime is n/d^2 → α, with κ > 1 and a dimension-independent subgaussian bound.
- 1.1 Main results: Below α⋆(κ), an ellipsoid fitting all points exists with probability tending to one and can be chosen well-conditioned.The fit satisfies mI_d ⪯ R ⪯ MI_d for constants depending on α and κ.
- 1.1 Main results: Above α⋆(κ), no positive semidefinite ellipsoid fit exists with probability tending to one, and the optimal squared fitting error converges to a positive limit.For α > α⋆(κ), e⋆(α, κ) > 0 and the fitting error is bounded away from zero with high probability.
- 1.1.1 The Gaussian model and explicit formula: For Gaussian data, κ = 3 yields the threshold α⋆(3) = 1/4, resolving the Gaussian ellipsoid fitting conjecture.The paper also shows α⋆(κ) → 1/2 as κ ↓ 1 and that the transition is continuous in the optimal squared error.
- 1.1.2 Universality and exact fitting: Approximate fitting has broader universality than exact fitting, while exact fitting requires additional anti-concentration and can fail for dependent-coordinate distributions.A distribution with a zero vector occurring with high probability provides an obstruction to exact fitting when n ≍ d^2.
2 Proof overview
The proof combines approximate fitting, uniform small-residual interpolation, and a head–tail decomposition to establish exact fitting below the threshold and infeasibility above it. A nuclear-norm lower bound and anti-concentration estimates supply the central technical control.
- Proof overview: SAT instances are defined by existence of an ellipsoid fit, while AXR = 0 characterizes constant quadratic values and a positive-definite kernel element yields an exact fit.The proof first constructs a well-conditioned approximate fit with small ℓ2 and ℓ∞ residuals, then corrects it exactly.
- Small-residual interpolation: The central challenge is proving exact fit, because the approximate residual depends on the same data that define AX.Uniform control over all residuals in Range(AX), rather than a fixed deterministic residual, is required.
- Small-residual interpolation: A naive residual interpolation inequality fails even for fixed λ, due to a sparse head and dense tail obstruction.The proof therefore decomposes λ into head and tail components and measures them in different norms.
- Nuclear-norm lower bound: Theorem 2.3 establishes, for α < 1/2, a uniform head–tail decomposition with a sparse set of O(d log d) largest coordinates and controlled tail behavior.Its proof uses shelling ideas from sparse recovery and is a main technical challenge.
- Small-residual interpolation: Anti-concentration is needed for exactification, and Proposition 2.4 applies without density assumptions, including discrete random variables.This distinguishes exact fitting from approximate fitting, which relies on concentration estimates.
- Universality and UNSAT: The proof transfers Gaussian least-squares behavior by barrier-regularized universality, while the UNSAT direction follows when the limiting squared loss is positive.Self-concordant barriers keep constrained optimizers interior and enable the required Lindeberg expansions.
3 Proof of the nuclear norm lower bound
This section proves the nuclear-norm lower bound through a priori quadratic-feature estimates, sparse interpolation, and a uniform lower bound for light tails. Sequential block revealing extends the argument to the full range α < 1/2.
- Anti-concentration: The light-tail analysis uses vector small-ball estimates, Gaussian regularization, Brascamp–Lieb inequalities, and covariance control.These ingredients produce density and small-ball bounds needed for uniformity over tails.
- A priori estimates: Proposition 3.1 supplies simultaneous high-probability estimates for the quadratic-feature matrix W and its restricted submatrices.The proof uses Hanson–Wright concentration, subexponential restricted-isometry estimates, norm concentration, and operator-norm bounds.
- Sparse vectors: For vectors supported on O(d log d) coordinates, Proposition 3.3 constructs an interpolating matrix and obtains the required nuclear-norm lower bound.Nuclear/operator norm duality converts the constructed matrix into the lower bound.
- Light tails: Proposition 3.4 lower-bounds the light-tail quotient norm uniformly over sparse sets and K-light tails when n/d^2 → α < 1/2.The sparse correction is constrained by an ℓ1 bound proportional to d^2/3 times the tail ℓ2 norm.
- Sequential block revealing: A single rectangular block closes the union bound only for α < 1/4, so sequential block revealing is required for general α < 1/2.The block loss approaches ((1 − 1/L)/2)d^2, and choosing L sufficiently large yields the full range.
4 Proof of the least-squares universality theorem
The least-squares universality proof compares regularized constrained problems for quadratic features and Gaussian features using a self-concordant barrier and leave-one-out expansions. Regularity estimates then permit removal of the ridge and transfer of the Gaussian limit.
- Conclusion: Removing ridge regularization and combining the universality comparison with the Gaussian characterization proves the stated least-squares universality theorem.The Gaussian matrices are non-isotropic for general κ, so their asymptotic value is characterized using a convex Gaussian min–max theorem.
- Leave-one-out analysis: Leave-one-out optimizers are compared with unconstrained quadratic approximations through Bregman-divergence and Hessian estimates.The analysis controls optimizer changes, residual terms, and inverse-Hessian blocks after inserting one feature.
- Feature regularity: The proof establishes feature regularity from approximate tensorization of variance and moment estimates for linear and quadratic functions.For quadratic features, the resulting regularity parameter satisfies τ_d = O(d^-1/2).
- Gaussian reference: The Gaussian approximate fit is well-conditioned, lies in the bounded matrix domain, and has zero empirical loss.This Gaussian input is used as the reference problem for transferring the least-squares asymptotics.
5 The Gaussian feature model
The Gaussian model reduces ellipsoid fitting through Gaussian-process and convex-geometry tools to a scalar variational problem governed by shifted GOE cone projections. This analysis identifies the threshold, its spectral optimizer, and the distinct constructions needed in SAT and UNSAT regimes.
- Reduction to Gaussian optimization: Gaussian process techniques and convex geometry rewrite the fitting problem as a Gaussian matrix acting on a rescaled positive-semidefinite cone, then apply CGMT.The CGMT compares a primary optimization involving a Gaussian matrix with an easier auxiliary optimization.
- Cone geometry: The transformed cone is obtained by an invertible diagonal rescaling, while κ = 3 is self-dual and satisfies T3 = I and cκ = 0.For general κ, the involution κ∨ = 1 + 4/(κ −1) exchanges the cases below and above 3.
- Scalar variational problem: The asymptotic optimization is determined by χκ(ζ), obtained from the projection of a shifted GOE matrix onto the rescaled positive-semidefinite cone.The map ζ 7→χκ(ζ) is nondecreasing and strictly increasing wherever positive, enabling unique level-crossing parameters.
- Threshold: The threshold satisfies 0 ≤ α⋆(κ) ≤ 1/2, with α⋆(κ) →0 as κ →∞ and α⋆(κ) →1/2 as κ →1.Its formula is defined through the scalar variational problem and the corresponding unique solution of the spectral equations.
- Spectral interpretation: For κ = 3, the limiting spectral law clips the semicircle at ω, places the mass below the cutoff at zero, and shifts and rescales the remainder onto the positive axis.At criticality, the law has an atom of mass 1/2 at zero and the rescaled positive half of the semicircle law.
- SAT and UNSAT regimes: Below α⋆(κ), a well-conditioned exact fit exists with high probability, whereas above α⋆(κ), the optimal squared loss is positive and no exact fit exists.The below-threshold fit has eigenvalues bounded between constants m and M; the limiting squared loss has a continuous first derivative and discontinuous second derivative.
A Extra corollaries, obstructions, and numerics
The appendix records consequences of the universality theorem, obstructions to exact ellipsoid fitting, and numerical details outside the phase-transition proof.
- The appendix collects an abstract universality consequence, exact-fitting obstructions, and numerical details not used in proving the phase transition.
A.1 Dual certificates and interpretation
The appendix gives a dual-certificate interpretation of the fitting residual and explains geometrically why positive definiteness distinguishes genuine ellipsoids from degenerate fits. In the UNSAT regime, positive residual energy is equivalent to a separating sample reweighting.
- Geometric interpretation: Singular positive-semidefinite matrices define cylindrical degenerations, because their quadratic sublevel sets are unrestricted along the kernel.Positive definiteness is what distinguishes the genuine ellipsoid obtained in the SAT theorem from a degenerate fit.
- Dual certificates: In the UNSAT regime, the positive least-squares energy has an exact dual interpretation through sample reweighting.This interpretation is formalized by the dual certificate identity.
- Dual certificates: A positive residual ΓX > 0 holds if and only if a centered unit-norm vector λ provides a strict positive-definite separating certificate.The normalized optimal residual itself supplies such a certificate when ΓX > 0.
A.2 A general-domain universality consequence
The general-domain result transfers optimization guarantees from centered Gaussian features to matching regular features with controlled covariance. A self-concordant barrier and anchor-based comparison yield expectation and probability bounds.
- Universality setup: For bounded convex domains with a self-concordant barrier, the framework compares a regular feature array W with its matching centered Gaussian feature array G.The result assumes finite feature regularity, positive covariance operator norm, and independent identically distributed samples.
- Universality consequence: The expected difference between regular-feature and Gaussian optimizations is controlled by C∆n, while the probability tail is bounded by C(1 + β−1)2K2ref/(nt2).The expectation result follows by taking expectations in the comparison inequality, and the probability result uses variance control and Chebyshev’s inequality.
- Comparison bound: The comparison error is bounded by an anchor term, barrier-removal cost, and a deterministic approximation term.The displayed bound controls ΦZ(D, B; β, γ) − ΦZ(D; β) using εFZ(θref, bref; β), γB(θref), and γϑ log(1/ε).
A.3 Why approximate fitting does not imply exact fitting
Regular-feature conditions and strong concentration controls do not guarantee exact ellipsoid fitting: low-dimensional geometric structure can force a positive residual. The obstruction persists for discrete atoms and nonatomic distributions supported on low-degree algebraic curves.
- Discrete obstruction: Adding rare copies of ±Id/d to a Gaussian background preserves covariance and regular-feature estimates but rules out exact centered fitting when both signs occur.Every trace-normalized matrix pairs with the two atoms as 1 and −1.
- Regularity is insufficient: Regular features with Kfeat = Oκ(1) and τd = Oκ(d−1/2) can still yield no exact fit when n/d2 → α > 0.The constructed random features have prescribed mean and covariance yet, with probability tending to one, no exact interpolation exists.
- Discrete obstruction: Signed atoms ±vd force opposite row values, producing a best normalized residual of order d−1/2 and fitting energy of order d−1.The residual lower bound follows from the limiting counts of positive and negative atoms.
- Geometric obstruction: A centered ellipsoid intersects a noncontained algebraic curve of degree D in at most 2D distinct real affine points.Projective Bézout bounds the total intersection multiplicity, including complex points, points at infinity, and tangencies.
- Probabilistic obstruction: For a mixture with curve mass pd, exact fitting fails with high probability when npd →∞ and Dd = o(npd).The curve observations are almost surely distinct, while any fitting ellipsoid can contain at most 2Dd of them.
- Probabilistic obstruction: A fixed positive curve mass with D = d and n ≍ d2 produces order d2 curve observations, exceeding the ellipsoid’s 2d-point intersection limit.The degree-one line case already retains isotropy and dimension-free subgaussian linear marginals, so those properties do not prevent the obstruction.
A.4 Nuclear-norm minimizers below the SAT threshold
The paper studies nuclear-norm minimization among exact affine fits and quantifies why minimizers are nearly positive semidefinite when a PSD feasible point exists. The mechanism combines a PSD competitor, trace control, and spectral decomposition.
- Setup: A PSD exact fit bounds the nuclear norm of every minimizer, making the nuclear-norm program feasible and controlling its size.The comparison uses a positive semidefinite competitor satisfying the interpolation constraints.
- Mechanism: The identity ∥S∥∗ − Tr S = 2∥S−∥∗ converts nuclear-norm and trace control into a bound on the minimizer’s negative spectral part.Here S = S+ − S− is the spectral decomposition into positive and negative parts.
- Conclusion: The resulting approximation establishes that nuclear-norm exact fits are almost PSD under the stated covariance-closeness assumption.
Consider the exact nuclear-norm program
The exact nuclear-norm program is feasible below the SAT threshold, and its minimizers have quantitatively small negative parts. With trace normalization, every minimizer is positive semidefinite.
- Approximate positivity: Every minimizer satisfies |Tr Ŝ − d| and ∥Ŝ−∥∗ bounded by δd/(1 − δ) when the empirical covariance is within δ of the identity.The nuclear-norm bound comes from a PSD competitor, while averaging the interpolation constraints controls the trace.
- Feasibility: Below α⋆(κ), the exact nuclear-norm program is feasible with probability tending to one.This follows from the SAT theorem’s positive semidefinite feasible point.
- Uniformity: Sample-covariance concentration makes the approximation and ratio bounds hold uniformly over the minimizer set.The resulting trace estimate is Tr Ŝ = d + O_P(…).
- Exact positivity: Below α⋆(κ), every trace-normalized nuclear-norm minimizer is positive semidefinite with probability tending to one.Rescaling a positive definite feasible point gives a PSD feasible point of nuclear norm d; equality of nuclear norm and trace forces positivity.
A.5 Numerical experiments
The numerical experiments construct coordinate distributions with prescribed fourth moment and estimate the largest feasible sample ratio by repeated SDP solves. The observed feasibility boundary is compared with the theoretical curve α⋆(κ).
- Distributions: For 1 ≤ κ ≤ 3, the experiments use a location mixture of two Gaussians, with κ = 3 interpreted as the Gaussian limit.The construction has fourth moment κ.
- Distributions: For κ ≥ 3, the experiments use a scale mixture whose direct moments satisfy EA2 = 1, EA4 = κ/3, and Eξ4 = κ.The location and scale mixture families agree at κ = 3, where the standard Gaussian is used.
- Experimental design: The study tests κ values from 1.05 through 30 using eight independent trials per value and nested samples with binary search over n.The search estimates the largest prefix for which ellipsoid fitting is numerically feasible.
- Experimental design: Feasibility is certified by a nonnegative spectral margin up to tolerance 10−5 using CVXPY and CLARABEL.The optimum is the largest certified spectral margin.
- Reported comparison: Figure 1 reports each trial’s largest feasible n/d2, their mean, middle 50 percent interval, and the theoretical curve α⋆(κ).