We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: how closely can we approximate the set of unit-trace $n times n$ PSD matrices, denoted by $D$, using at most $N$ number of $k times k$ PSD constraints? In this paper, we prove lower bounds on $N$ to achieve a good approximation of $D$ by considering two constructions of an approximating set. First, we consider the unit-trace $n times n$ symmetric matrices that are PSD when restricted to a fixed set of $k$-dimensional subspaces in $mathbb{RR}^n$. We prove that if this set is a good approximation of $D$, then the number of subspaces must be at least exponentially large in $n$ for any $k = o(n)$. % Second, we show that any set $S$ that approximates $D$ within a constant approximation ratio must have superpolynomial $mathbf{S}_+^k$-extension complexity. To be more precise, if $S$ is a constant factor approximation of $D$, then $S$ must have $mathbf{S}_+^k$-extension complexity at least $exp( C cdot min { sqrt{n}, n/k })$ where $C$ is some absolute constant. In addition, we show that any set $S$ such that $D subseteq S$ and the Gaussian width of $D$ is at most a constant times larger than the Gaussian width of $D$ must have $mathbf{S}_+^k$-extension complexity at least $exp( C cdot min { n^{1/3}, sqrt{n/k} })$. These results imply that the cone of $n times n$ PSD matrices cannot be approximated by a polynomial number of $k times k$ PSD constraints for any $k = o(n / log^2 n)$. These results generalize the recent work of Fawzi on the hardness of polyhedral approximations of $mathbf{S}_+^n$, which corresponds to the special case with $k=1$.
Download