Weak $(1-\epsilon )$-nets for polynomial superlevel sets

Abstract

We prove that for any Borel probability measure $\mu$ on ${\mathbb{R}}^n$ there exists a set $X\subset {\mathbb{R}}^n$ of $n+1$ points such that any $n$-variate quadratic polynomial $P$ that is nonnegative on $X$ (i.e. $P(x)\ge 0$, for every $x\in X$) satisfies $\mu \{P\ge 0\}\ge \frac{2}{(n+1)(n+2)}$. We also prove that given an absolutely continuous probability measure $\mu$ on ${\mathbb{R}}^n$ and $D\le 2k$, for every $\delta >0$ there exists a set $X\subset {\mathbb{R}}^n$ with $|X|\le \left(\genfrac{}{}{0ex}{}{n+2k}{n}\right)-n-1$ such that any $n$-variate polynomial $P$ of degree $D$ that is nonnegative on $X$ satisfies $\mu \{P\ge 0\}\ge \frac{1}{\left(\genfrac{}{}{0ex}{}{n+2k}{n}\right)+1}-\delta$. These statements are analogues of the celebrated centerpoint theorem, which corresponds to the case of linear polynomials. Our results follow from new estimates on the Carathéodory numbers of real Veronese varieties, or alternatively, from bounds on the nonnegative symmetric rank of real symmetric tensors.

3 figures