On Approximating Positive Semidefinite Cone Using Small-sized PSD Constraints

We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a convex 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$ positive semidefinite (PSD) matrices, denoted by $D$, using at most $N$ number of $k \times k$ PSD constraints?" We show that any set that approximates $D$ within a constant approximation ratio must have superpolynomially large $k$-semidefinite extension complexity when $k = o(n / \log n)$.