A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points
This resolves a long-standing conjecture in theoretical machine learning with implications for sum-of-squares lower bounds, though it is incremental as it addresses logarithmic factors.
The paper tackles the problem of determining how many random Gaussian points in high dimensions lie on a common ellipsoid, proving that with high probability, a set of c d^2/log^4(d) points do so, nearly confirming a conjecture within logarithmic factors.
We prove that for $c>0$ a sufficiently small universal constant that a random set of $c d^2/\log^4(d)$ independent Gaussian random points in $\mathbb{R}^d$ lie on a common ellipsoid with high probability. This nearly establishes a conjecture of~\cite{SaundersonCPW12}, within logarithmic factors. The latter conjecture has attracted significant attention over the past decade, due to its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.