Ellipsoid Fitting Up to a Constant
share
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 v_1, v_2, …, v_m with high probability when the v_is 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^⊤X v_i =1 for every 1 ≤ i ≤ m - 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 m ≥ d^2/log^O(1)(d) via certain explicit constructions. In this work, we give a substantially tighter analysis of their construction to prove that m ≥ 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.
READ FULL TEXT