Polynomial norms

In this paper, we study polynomial norms, i.e., norms that are the dth root of a degree-d homogeneous polynomial f. We first show that a necessary and sufficient condition for f ¹ /d to be a norm is for f to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from dth 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.