Approximating Nonnegative Polynomials via Spectral Sparsification

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 showthat for fixed $m\ge 3$, all linear $m$ dimensional sections of the nonnegative cone that include $(x_1^2+x_2^2+\ldots

• x_n^2)^d$hasacostantratiopolyhedralapproximationwith$O(n^{m-2})$ many facets. Our approach is convex geometric, and parts of the argument rely on the recent solution of Kadison-Singer problem. We also discuss a randomized polyhedral approximation which might be of independent interest.