  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^{\top}X v_i =1$ for every $1 \leq i \leq 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 \geq 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 \geq 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.
