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

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 $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$.

33 pages, 4 figures

References in corpus (1)

• Lifting for Simplicity: Concise Descriptions of Convex Sets

Cited by in corpus (3)

• Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
• Extreme Nonnegative Quadratics over Stanley Reisner Varieties
• On the quality of the $k-$PSD closure approximation