# Antoine Maillard (FIM (Institute for Mathematical Research) and the department of mathematics at ETH Zurich)

When |
Nov 22, 2023
from 01:00 to 02:00 |
---|---|

Where | M7 101 |

Attendees |
Antoine Maillard |

Add event to calendar |
vCal iCal |

**Speaker:** Antoine Maillard

**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 Afonso Bandeira, Tim Kunisky, Shahar Mendelson and Elliot Paquette.

In Room M7 101