Fitting an ellipsoid to random points: predictions using the replica method
Antoine Maillard, Dmitriy Kunisky
cond-mat.dis-nn, cond-mat.stat-mech, cs.DS, math.PR, math.ST
2023-10-02
Replica analysis puts the SAT/UNSAT transition for fitting a centered ellipsoid to n Gaussians in R^d at α=n/d²=1/4; nuclear-norm minimization covers the SAT phase.
Take n standard Gaussian points in R^d. Is there a centered ellipsoid whose boundary passes through every one of them? As a semidefinite program: find S ⪰ 0 with xμ^T S xμ = d. The high-dimensional scaling is n, d → ∞ with n/d² → α > 0. Eigenvectors of S are the principal axes; after rescaling distances by √d, the unit sphere S = I has all axis lengths equal to 1.
The question entered statistics through Minimum Trace Factor Analysis, then picked up links to average-case discrepancy (an SDP relaxation of min{ε∈{±1}^d} ∥Aε∥∞) and overcomplete ICA. Numerics plus a Gaussian-measurement analogy produced a conjecture: SAT for α < 1/4, UNSAT for α > 1/4. Replace the rank-one matrices xx^T by GOE matrices and Gordon's escape-through-a-mesh theorem pins the transition at the statistical dimension of the PSD cone, which is d²/4. The real affine subspace is not uniformly oriented, so Gordon does not apply.
Rigorous SAT bounds climbed from n = O(d^{6/5-ε}) to O(d^{3/2-ε}) to O(d²/polylog d) to n ≤ d²/C for a large constant C. The only hard UNSAT bound is linear independence: α > 1/2. Allowing mean-squared error Θ(1/d) makes the sphere itself a fit and the problem collapses. Exact fitting keeps the sharp transition.
The feasible set is convex, so the Gibbs measure is log-concave and replica symmetry is the right ansatz: one cluster of solutions.
The volume of feasible S is encoded in a partition function Z. The free entropy Φ = lim (1/d²) E log Z is finite in the SAT phase and goes to −∞ at the transition. The replica trick computes integer moments E[Z^r], continues in r, and differentiates at r = 0. Overlaps Qab = (1/d) Tr[R^a R^b] are the order parameters. The effective integral over matrices produces an extensive-rank HCIZ integral, the spherical integral of exp(θ d/2 Tr[O R O^T Y]) over the orthogonal group. Its large-d limit depends only on the two spectral densities and is given by a Burgers equation that is painful to use. Near the SAT/UNSAT point the solution set shrinks to a point, θ → ∞, and a dilute expansion applies: the leading term is the alignment of ordered eigenvalues.
The same free entropy covers a family of explicit convex programs: minimize Tr[V(S)] on the linear constraints. V(x) = |x|^γ is a Schatten-γ objective (nuclear norm at γ = 1, Frobenius at γ = 2). V(x) = |x−1|^γ is a perturbation of the identity. The zero-temperature limit yields the spectrum of these minimizers.
For Gaussians the SAT/UNSAT point is α = 1/4.
This is the first analytical derivation of the conjectured threshold. Φ stays finite for α < 1/4 and Φ → −∞ as α ↑ 1/4.
For α < 1/4 a uniformly random feasible S has empirical spectral law μ[α] solving the replica equations. At the threshold that law tends to μc: an atom of mass 1/2 at zero, plus a quarter-circle of radius 3π/2 on [0, 3π/2]. About half the principal axes degenerate and the fit becomes an elliptic cylinder. Finite-d checks at d = 100, α = 0.24, 50 draws, find a fraction ≈ 0.52 of eigenvalues with |λ| < 10^{-3}. Imposing S ⪰ κ I lowers the threshold to some αc(κ) ≤ 1/4, with αc → 0 as κ → 1. Equivalently, every fit at a given α < 1/4 has a longest principal axis at least ℓ⋆(α) = [κ⋆(α)]^{-1/2}.
| Method | Threshold αc | Comparison |
| min ∥S∥ (nuclear) | 1/4 | entire SAT phase |
| min ∥S∥F (least squares) | 1/10 | prior numerics ≈ 1/17 |
| min ∥S − I∥F | 1/10 | same as least squares |
| min ∥S − I∥op | ≈ 0.1892 | still below 1/4 |
Nuclear-norm minimization is PSD throughout the SAT phase, and its spectrum matches the typical uniform solution. Past α = 1/4 the spectrum becomes two truncated semicircles plus an atom at zero. Least squares has a semicircular spectrum of mean 1 and variance 2α/(1−2α); the left edge hits zero at α = 1/10. The older 1/17 reading is more likely a finite-size effect.
For rotationally invariant vectors x = √χ ω with ω uniform on the sphere, the transition depends only on the norm fluctuation τ = lim d Var[∥x∥²/d]. Gaussians have τ = 2 and αc = 1/4. As τ → 0, αc → 1/2; as τ → ∞, αc → 0. Exactly frozen norms make the sphere a fit for every n.
The ellipsoid-fitting conjecture now has an analytical picture that sits on α = 1/4, and it separates existence from constructibility. Nuclear-norm SDP is the construction that, according to this calculation, works on the whole SAT interval; least squares only reaches 40% of that interval. Anyone using MTFA, discrepancy relaxations, or overcomplete ICA can treat these thresholds as design numbers.
A companion paper takes the free-entropy universality here (a uniform CLT for low-dimensional projections, mapping the problem onto a GOE measurement model) and proves a slightly relaxed almost-exact version of the transition at n ≃ d²/4.
The original exact problem is not settled in this manuscript. Near the transition typical rank is about d/2, so Grothendieck-style finite-rank reductions do not apply.
The replica method is not a proof. Analytic continuation of integer moments and the swap of d → ∞ with r → 0 remain unjustified. Results are labeled Claim. The companion theorem is for a modified problem.
The exact HCIZ formula is unused in practice; almost all analysis sits on the dilute expansion. Away from α = 1/4 the typical spectrum is only implicit. A (1−4α) expansion is left open. Non-rotationally-invariant directions are untouched. If ω is a single fixed vector, no ellipsoid fit exists. How much delocalization restores universality is open, as is the window where τ → 0 with d.
Numerics are d = 100 SDPs solved with Mosek. Conditioning worsens near α = 1/4. The nuclear-norm minimizer is, in the paper's phrasing, likely hard to characterize mathematically; turning that prediction into a rigorous existence proof is still a step away.