Near-optimal fitting of ellipsoids to random points

Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4235-4295, 2023.

Abstract

Given independent standard Gaussian points $v_1, \ldots, v_n$ 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, Saunderson, Parrilo, and Willsky [Proc. of Conference on Decision and Control, pp. 6031-6036, 2013] conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points $n$ increases, with a sharp threshold at $n \sim d^2/4$. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = d^2/\mathrm{polylog}(d)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix and a careful analysis of its Neumann expansion via the theory of graph matrices.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-potechin23a, title = {Near-optimal fitting of ellipsoids to random points}, author = {Potechin, Aaron and Turner, Paxton M. and Venkat, Prayaag and Wein, Alexander S.}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {4235--4295}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/potechin23a/potechin23a.pdf}, url = {https://proceedings.mlr.press/v195/potechin23a.html}, abstract = {Given independent standard Gaussian points $v_1, \ldots, v_n$ 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, Saunderson, Parrilo, and Willsky [Proc. of Conference on Decision and Control, pp. 6031-6036, 2013] conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points $n$ increases, with a sharp threshold at $n \sim d^2/4$. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = d^2/\mathrm{polylog}(d)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix and a careful analysis of its Neumann expansion via the theory of graph matrices. } }
Endnote
%0 Conference Paper %T Near-optimal fitting of ellipsoids to random points %A Aaron Potechin %A Paxton M. Turner %A Prayaag Venkat %A Alexander S. Wein %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-potechin23a %I PMLR %P 4235--4295 %U https://proceedings.mlr.press/v195/potechin23a.html %V 195 %X Given independent standard Gaussian points $v_1, \ldots, v_n$ 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, Saunderson, Parrilo, and Willsky [Proc. of Conference on Decision and Control, pp. 6031-6036, 2013] conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points $n$ increases, with a sharp threshold at $n \sim d^2/4$. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = d^2/\mathrm{polylog}(d)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix and a careful analysis of its Neumann expansion via the theory of graph matrices.
APA
Potechin, A., Turner, P.M., Venkat, P. & Wein, A.S.. (2023). Near-optimal fitting of ellipsoids to random points. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:4235-4295 Available from https://proceedings.mlr.press/v195/potechin23a.html.

Related Material