Fitting an ellipsoid to a quadratic number of random points

We consider the problem (P) of fitting n standard Gaussian random vectors in ℝd to the boundary of a centered ellipsoid, as n, d → ∞. This problem is conjectured to have a sharp feasibility transition: for any varepsilon > 0, if n ≤ (1 - varepsilon) d2 / 4 then (P) has a solution with high probability, while (P) has no solutions with high probability if n ≥ (1 + varepsilon) 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 / polylog(d). In this work, we improve over previous approaches using a key result of Bartl & 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.