Fitting an ellipsoid to a quadratic number of random points

Abstract

We consider the problem (P) of fitting n standard Gaussian random vectors in Rd to the boundary of a centered ellipsoid, as n, d → ∞. This problem is conjectured to have a sharp feasibility transition: for any ε > 0, if n ≤ (1 − ε)d2/4 then (P) has a solution with high probability, while (P) has no solutions with high probability if n ≥ (1 + ε)d2/4. So far, only a trivial bound n ≥ d2/2 is known on the negative side, while the best results on the positive side assume n ≤ d2/plog(d). In this work, we improve over previous approaches using a key result of Bartl and Mendelson (2022) on the concentration of Gram matrices of random vectors under mild assumptions on their tail behavior. This allows us to give a simple proof that (P) is feasible with high probability when n ≤ d2/C, for a (possibly large) constant C > 0.