Fitting an ellipsoid to a quadratic number of random points
Afonso S. Bandeira Antoine Maillard Shahar Mendelson Elliot Paquette
We consider the problem $(\mathrm{P})$ of fitting $n$ standard Gaussian
random vectors in $\mathbb{R}^d$ to the boundary of a centered ellipsoid, as
$n, d \to \infty$. This problem is conjectured to have a sharp feasibility
transition: for any $\varepsilon > 0$, if $n \leq (1 - \varepsilon) d^2 / 4$
then $(\mathrm{P})$ has a solution with high probability, while $(\mathrm{P})$
has no solutions with high probability if $n \geq (1 + \varepsilon) d^2 /4$. So
far, only a trivial bound $n \geq d^2 / 2$ is known on the negative side, while
the best results on the positive side assume $n \leq d^2 /
\mathrm{polylog}(d)$. In this work, we improve over previous approaches using a
key result of Bartl & Mendelson 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 $(\mathrm{P})$ is feasible with high probability when $n \leq
d^2 / C$, for a (possibly large) constant $C > 0$.