Speakers
Description
Jun-Ting Hsieh, Pravesh Kothari, Aaron Potechin and Jeff Xu
Abstract: Saunderson, Parrilo and Willsky asked the following elegant geometric question: what is the largest m = m(d) such that there is an ellipsoid in Rd that passes through v_1, v_2, . . . , v_m with high probability when 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 v_i^TXv_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 [10] and Kane and Diakonikolas [8] proved that m ≳ d^2 / log^{O(1)} (d) via a certain natural, explicit construction.
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. 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.