# Approximating Nonnegative Polynomials via Spectral Sparsification

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Dec 2016.

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

- [Approximate Real Symmetric Tensor Rank](https://mlsanity.com/paper/2207.12529/) (2022)

## Abstract (arXiv)

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 ≥ 3, all linear m dimensional sections of the nonnegative cone that include (x12+x22+ldots + xn2)d has a costant ratio polyhedral approximation with O(nm-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.