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

preprint2021arXivOpen access

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×nn \times n PSD matrices, denoted by DD, using at most NN number of k×kk \times k PSD constraints?" In this paper, we prove lower bounds on NN to achieve a good approximation of DD by considering two constructions of an approximating set. First, we consider the unit-trace n×nn \times n symmetric matrices that are PSD when restricted to a fixed set of kk-dimensional subspaces in RRn\mathbb{RR}^n. We prove that if this set is a good approximation of DD, then the number of subspaces must be at least exponentially large in nn for any k=o(n)k = o(n). % Second, we show that any set SS that approximates DD within a constant approximation ratio must have superpolynomial S+k\mathbf{S}_+^k-extension complexity. To be more precise, if SS is a constant factor approximation of DD, then SS must have S+k\mathbf{S}_+^k-extension complexity at least exp⁡(C⋅min⁡{n,n/k})\exp( C \cdot \min \{ \sqrt{n}, n/k \}) where CC is some absolute constant. In addition, we show that any set SS such that D⊆SD \subseteq S and the Gaussian width of DD is at most a constant times larger than the Gaussian width of DD must have S+k\mathbf{S}_+^k-extension complexity at least exp⁡(C⋅min⁡{n1/3,n/k})\exp( C \cdot \min \{ n^{1/3}, \sqrt{n/k} \}). These results imply that the cone of n×nn \times n PSD matrices cannot be approximated by a polynomial number of k×kk \times k PSD constraints for any k=o(n/log⁡2n)k = o(n / \log^2 n). These results generalize the recent work of Fawzi on the hardness of polyhedral approximations of S+n\mathbf{S}_+^n, which corresponds to the special case with k=1k=1.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.