A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points
Abstract
We prove that for $c>0$ a sufficiently small universal constant that a random set of $c d^2/\log^4(d)$ independent Gaussian random points in $\R^d$ lie on a common ellipsoid with high probability. This nearly establishes a conjecture of \citet{SaundersonCPW12}, within logarithmic factors.The latter conjecture has attracted significant attention over the past decade, dueto its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.
Cite
Text
Kane and Diakonikolas. "A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points." Conference on Learning Theory, 2023.Markdown
[Kane and Diakonikolas. "A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points." Conference on Learning Theory, 2023.](https://mlanthology.org/colt/2023/kane2023colt-nearly/)BibTeX
@inproceedings{kane2023colt-nearly,
title = {{A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points}},
author = {Kane, Daniel and Diakonikolas, Ilias},
booktitle = {Conference on Learning Theory},
year = {2023},
pages = {3014-3028},
volume = {195},
url = {https://mlanthology.org/colt/2023/kane2023colt-nearly/}
}