A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points

We prove that for c>0 a sufficiently small universal constant that a random set of c d2/log4(d) independent Gaussian random points in ℝd lie on a common ellipsoid with high probability. This nearly establishes a conjecture of~citeSaundersonCPW12, 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.