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

arXiv: https://arxiv.org/abs/2105.02080 · HTML: https://mlsanity.com/paper/2105.02080/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2021.

## Built on by (most cited first, 1 of 1)

- [Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations](https://mlsanity.com/paper/2511.21890/) (2025)

## Abstract (arXiv)

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.