On Approximations of the PSD Cone by a Polynomial Number of Smaller-sized PSD Cones

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 × n PSD matrices, denoted by D, using at most N number of k × 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 × n symmetric matrices that are PSD when restricted to a fixed set of k-dimensional subspaces in mathbbRRn. 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 S_+k-extension complexity. To be more precise, if S is a constant factor approximation of D, then S must have S_+k-extension complexity at least exp( C · min √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 S_+k-extension complexity at least exp( C · min n1/3, √n/k ). These results imply that the cone of n × n PSD matrices cannot be approximated by a polynomial number of k × k PSD constraints for any k = o(n / log2 n). These results generalize the recent work of Fawzi on the hardness of polyhedral approximations of S_+n, which corresponds to the special case with k=1.