Polynomial norms

In this paper, we study polynomial norms, i.e., norms that are the $d$th root of a degree-$d$ homogeneous polynomial $f$. We first show that a necessary and sufficient condition for $f^{1/d}$ to be a norm is for $f$ to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from $d$th roots of polynomials, we prove that any norm can be approximated arbitrarily well by a polynomial norm. We then investigate the computational problem of testing whether a form gives a polynomial norm. We show that this problem is strongly NP-hard already when the degree of the form is 4, but can always be answered by solving a hierarchy of semidefinite programs. We further study the problem of optimizing over the set of polynomial norms using semidefinite programming. To do this, we introduce the notion of $r$-sum of squares-convexity and extend a result of Reznick on sum of squares representations of positive definite forms to positive definite biforms. We conclude with some applications of polynomial norms to statistics and dynamical systems.