There are significantly more nonegative polynomials than sums of squares

By Grigoriy Blekherman. 2003

137 citations recorded by the source corpus.

We study the quantitative relationship between the cones of nonnegative polynomials, cones of sums of squares and cones of sums of even powers of linear forms. We derive bounds on the volumes (raised to the power reciprocal to the ambient dimension) of compact sections of the three cones. We show that the bounds are asymptotically exact if the degree is fixed and number of variables tends to infinity. When the degree is larger than two, it follows that there are significantly more nonnegative polynomials than sums of squares and there are significantly more sums of squares than sums of even powers of linear forms. Moreover, we quantify the exact discrepancy between the cones; from our bounds it follows that the discrepancy grows as the number of variables increases.

Subfields: Applied Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/47c232ec760fab278c65c3f447e3400cfd95973e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Numerical Analysis

Citations in the corpus

Sums of Squares, Moment Matrices and Optimization Over Polynomials (2009, background): “[14] There exist constants C1, C2 > 0 depending on d only such that for any n large enough,”
On Hilbert's construction of positive polynomials (2007, background): “Recently, Blekherman [3] has shown that for fixed degree m, the “probability” that a psd form is sos goes to 0 as n increases.”
LMI Techniques for Optimization Over Polynomials in Control: A Survey (2010, background): “Moreover, SOS polynomials are dense among positive polynomials, but they become sparse by ﬁxing the degree and increasing the number of variables [16], [17].”