Universality and sharp thresholds for ellipsoid fitting
Data Structures and AlgorithmsMachine Learning
Summary
The authors studied when you can fit a positive definite ellipsoid exactly around a set of random points with independent, similar-shaped distributions. They found a clear cutoff point based on how many points and the dimension size relate, which determines if such an ellipsoid exists. Below this threshold, the ellipsoid can pass through all points with high probability; above it, no such fit is possible. The threshold depends only on a specific property of the data's distribution called the fourth moment, showing a type of universality. For normal Gaussian data, the authors confirmed this threshold to be 1/4, solving a previously known problem.
Authors
Frederic Koehler, Youngtak Sohn
Abstract
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.