Squared polynomial approximation kernels for the hypercube: improved error bounds and implications for Lasserre hierarchies

Abstract

We propose a new family of polynomial approximation kernels for approximating nonnegative polynomials on the hypercube $[-1,1{]}^n$. Our Kernels produce polynomial sums-of-squares of degree $r$, achieving an $O({\log }^{3}r/r^2)$ error in the ${\ell }_1$-norm of the coefficients. This improves on the known error bound $O(1/r)$ from the literature. As a corollary, we obtain an improved convergence rate for the Lasserre hierarchy for polynomial optimization on the hypercube, again improving a known rate by Baldi and Slot from $O(1/r)$ to $O({\log }^{3}r/r^2)$.

17 pages