Approximating Nonnegative Polynomials via Spectral Sparsification
研究用多面体逼近非负多项式锥，证明任何常数比逼近都需要指数多个面，但对固定维数的线性截面只需多项式多个面，方法涉及凸几何和Kadison-Singer问题的解。
We study polyhedral approximations to the cone of nonnegative polynomials. We show that any constant ratio polyhedral approximation to the cone of nonnegative degree $2d$ forms in $n$ variables has to have exponentially many facets in terms of $n$. We also show that for any fixed $m \geq 3$, all linear $m$-dimensional sections of the nonnegative cone that include $(x_1^2+x_2^2+\cdots + x_n^2)^d$ have a constant ratio polyhedral approximation with $O(n^{m-2})$ many facets. Our approach is convex geometric, and parts of the argument rely on the recent solution of the Kadison--Singer problem. We also discuss a randomized polyhedral approximation which might be of independent interest.