Theory Lunch Seminar
— 1:00pm
Speaker:
PRAYAAG VENKAT
,
Ph.D. Student, Theory of Computation Group, Harvard University
https://vprayaag.github.io/
On fitting ellipsoids to random points
Given n independent standard Gaussian points in dimension d, for what values of (n, d) does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of the points? This basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. Based on strong numerical evidence, it is conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points n increases, with a sharp threshold at n ~ (d^2)/4. In this talk, I will discuss an approach towards resolving this conjecture and prove the existence of a fitting ellipsoid for some n = \Omega(d^{3/2}). Based on joint work Paxton Turner and Alex Wein.
In Person and Zoom Participation. See announcement.
Event Website:
https://www.cs.cmu.edu/~theorylunch/