Ellipsoid Fitting Up to a Constant

MaRDI QIDQ6443446zbMATH OpenFDO

Authors Jun-Ting Hsieh, Pravesh Kothari, Aaron Potechin, Jeff Xu

Publication date 12 July 2023

Abstract: In [Sau11,SPW13], Saunderson, Parrilo and Willsky asked the following elegant geometric question: what is the largest $m=m(d)$ such that there is an ellipsoid in $mathbb{R}^d$ that passes through $v_1,v_2,ldots,v_m$ with high probability when the $v_i$s are chosen independently from the standard Gaussian distribution $N(0,I_d)$. The existence of such an ellipsoid is equivalent to the existence of a positive semidefinite matrix $X$ such that $v_i^{op}X{v}_i=1$ for every $1leqileqm$ - a natural example of a random semidefinite program. SPW conjectured that $m=(1-o(1))d^2/4$ with high probability. Very recently, Potechin, Turner, Venkat and Wein and Kane and Diakonikolas proved that $mgeq{d}^2/lo{g}^{O(1)}(d)$ via certain explicit constructions. In this work, we give a substantially tighter analysis of their construction to prove that $mgeq{d}^2/C$ for an absolute constant $C>0$. This resolves one direction of the SPW conjecture up to a constant. Our analysis proceeds via the method of Graphical Matrix Decomposition that has recently been used to analyze correlated random matrices arising in various areas [BHK+19]. Our key new technical tool is a refined method to prove singular value upper bounds on certain correlated random matrices that are tight up to absolute dimension-independent constants. In contrast, all previous methods that analyze such matrices lose logarithmic factors in the dimension.

This page was built for publication: Ellipsoid Fitting Up to a Constant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443446)