Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes a sharp phase transition in the problem of fitting random vectors with independent subgaussian coordinates to an ellipsoid, identifying a specific threshold for satisfiability. Below this threshold, a positive definite ellipsoid can fit all data points with high probability, while above it, no positive semidefinite fit is possible. The authors also derive the optimal squared fitting error in the unsatisfiable regime, highlighting a universality phenomenon dependent solely on the common fourth moment of the coordinate distributions, with the threshold for standard Gaussian data being $1/4$.
A clear threshold reveals that fitting ellipsoids can succeed or fail dramatically based on a single statistical moment, reshaping our understanding of high-dimensional data fitting.
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.