Abstract
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 PSD matrices, denoted by , using at most number of PSD constraints?" In this paper, we prove lower bounds on to achieve a good approximation of by considering two constructions of an approximating set. First, we consider the unit-trace symmetric matrices that are PSD when restricted to a fixed set of -dimensional subspaces in . We prove that if this set is a good approximation of , then the number of subspaces must be at least exponentially large in for any . % Second, we show that any set that approximates within a constant approximation ratio must have superpolynomial -extension complexity. To be more precise, if is a constant factor approximation of , then must have -extension complexity at least where is some absolute constant. In addition, we show that any set such that and the Gaussian width of is at most a constant times larger than the Gaussian width of must have -extension complexity at least . These results imply that the cone of PSD matrices cannot be approximated by a polynomial number of PSD constraints for any . These results generalize the recent work of Fawzi on the hardness of polyhedral approximations of , which corresponds to the special case with .
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.