On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
复制标题
通过多项式较小尺寸 PSD 锥体来逼近 PSD 锥体
作者：
Dogyoon Song;P. Parrilo
研究了半正定(PSD)矩阵的锥用可用较小尺寸的PSD约束来描述的锥逼近问题。具体地说，我们问这样一个问题：“我们能以多大程度上逼近由D表示的单位迹n$$n×n PSD矩阵的集合，使用至多N个$$k imes k$$k×k PSD约束？”在这篇文章中，我们通过考虑两种逼近集的构造，证明了N的下界，以达到对D的良好逼近。首先，我们考虑单位迹n$$n×n对称矩阵，当限制在$${mathbb{R}}^n$$Rn中k维子空间的固定集合时，它们是PSD的。我们证明了如果这个集合是D的一个很好的逼近，那么对于任何$$k=o(N)$$k=o(N)，子空间的个数一定至少是n的指数大的。其次，证明了在一个常逼近比内逼近D的任何S集必有超多项式${varvec{S}}_+^k$$S+k-扩张复杂性。更准确地说，如果S是D的一个常数因子逼近，则S一定有$${varvec{S}}_+^k$$S+k-扩张复杂性至少$$exp(CCDOT min{SQRT{n}，n/k})$$exp(C·min{n，n/k})，其中C是某个绝对常数。此外，我们还证明了，任何集合S若满足$$D子集S$$D⊆S且S的高斯宽度至多是D的高斯宽度的常数倍，则必有$${varvec{S}}_+^k$$S+k-扩张复杂度至少$$exp(Ccdotmin{n^{1/3}，sqrt{n/k}})$exp(C·min{n 1/3，n/k})。这些结果表明，对于任意$$k=o(n/log^2 n)$$k=o(n/log2 n)，$$n imes n$$n×n PSD矩阵的锥不能用$$k imes k$$k×k PSD约束的多项式数逼近.这些结果推广了Fawzi(Math Oper Res 46(4)：1479-1489,2021年)关于$${varvec{S}}_+^n$$S+n的多面体逼近的硬度的工作，它对应于$$k=1$$k=1的特例。
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 imes n$$ n × n PSD matrices, denoted by D , using at most N number of $$k imes k$$ 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 imes n$$ n × n symmetric matrices that are PSD when restricted to a fixed set of k -dimensional subspaces in $${mathbb {R}}^n$$ R 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)$$ k = o ( n ) . Second, we show that any set S that approximates D within a constant approximation ratio must have superpolynomial $${varvec{S}}_+^k$$ S + k -extension complexity. To be more precise, if S is a constant factor approximation of D , then S must have $${varvec{S}}_+^k$$ S + k -extension complexity at least $$exp ( C cdot min { sqrt{n}, n/k })$$ 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$$ D ⊆ S and the Gaussian width of S is at most a constant times larger than the Gaussian width of D must have $${varvec{S}}_+^k$$ S + k -extension complexity at least $$exp ( C cdot min { n^{1/3}, sqrt{n/k} })$$ exp ( C · min { n 1 / 3 , n / k } ) . These results imply that the cone of $$n imes n$$ n × n PSD matrices cannot be approximated by a polynomial number of $$k imes k$$ k × k PSD constraints for any $$k = o(n / log ^2 n)$$ k = o ( n / log 2 n ) . These results generalize the recent work of Fawzi (Math Oper Res 46(4):1479–1489, 2021) on the hardness of polyhedral approximations of $${varvec{S}}_+^n$$ S + n , which corresponds to the special case with $$k=1$$ k = 1 .
PSD 锥体的稀疏 PSD 近似
影响因子：
2.7
作者：
Blekherman, Grigoriy;Dey, Santanu S.;Molinaro, Marco;Sun, Shengding
通讯作者：
Sun, Shengding