11:30 am–12:30 pm
DSI 105 5460 S. University Ave.
Frederic Koehler
DSI/Department of Statistics
University of Chicago
Title: A Least-Squares Perspective on Ellipsoid Fitting
Abstract: Suppose we have n i.i.d. random vectors X_1,\ldots, X_n in d dimensions. How large can n be, as a function of d, such that there exists an ellipsoid interpolating all n points? Saunderson, Parrilo, and Willsky conjectured an explicit answer (n ~ d^2/4) for Gaussian data. Subsequently, many authors made rigorous progress on this question. We study a natural least-squares generalization of ellipsoid fitting, over a general class of data distributions, and solve its high-dimensional limit --- this proves the Gaussian conjecture as a special case. The solution combines in a nice way ideas from high-dimensional probability, statistical learning, and convex geometry + optimization.
Based on a joint work with Youngtak Sohn.