Ellipsoid Fitting Up to a Constant

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 ℝd that passes through v1, v2, ldots, vm with high probability when the vis are chosen independently from the standard Gaussian distribution N(0,Id). The existence of such an ellipsoid is equivalent to the existence of a positive semidefinite matrix X such that vitopX vi =1 for every 1 ≤ i ≤ m - a natural example of a random semidefinite program. SPW conjectured that m= (1-o(1)) d2/4 with high probability. Very recently, Potechin, Turner, Venkat and Wein and Kane and Diakonikolas proved that m ≥ d2/logO(1)(d) via certain explicit constructions. In this work, we give a substantially tighter analysis of their construction to prove that m ≥ d2/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.