Fitting ellipsoids to random points

11/08/2023 3:30 pm - 4:30 pm
Benjamin McKenna Changji Xu Kevin Yang
virtual

Probability Seminar

Speaker: Antoine Maillard (ETH Zürich)

Title: Fitting ellipsoids to random points

Abstract: We consider the problem of exactly fitting an ellipsoid (centered at 0) to n standard Gaussian random vectors in dimension d, for very large n and d. This problem has connections to questions in statistical learning and theoretical computer science, and is conjectured to undergo a sharp transition: with high probability, it has a solution if n < d^2/4, while it is not satisfiable if n > d^2/4. In this talk we will discuss the origin of this conjecture, and highlight some recent progress, in three different directions:

  • A proof that the problem is feasible for n < d^2 / C, for some (large) constant C, significantly improving over previously-known bounds.
  • A non-rigorous characterization of the conjecture, as well as significant generalizations, using analytical methods of statistical physics.
  • A rigorous proof of a satisfiability transition exactly at n = d^2 / 4 in a slightly relaxed version of the problem, the first rigorous result characterizing the expected phase transition in ellipsoid fitting. The proof is inspired by the non-rigorous characterization discussed above.

This talk is based on the three manuscripts: arXiv:2307.01181, arXiv:2310.01169, arXiv:2310.05787, which are joint works with A. Bandeira, Tim Kunisky, Shahar Mendelson and Elliot Paquette.