# Polynomial Norms

arXiv: https://arxiv.org/abs/1704.07462 · HTML: https://mlsanity.com/paper/1704.07462/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2017.

## Built on by (most cited first, 1 of 1)

- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)

## Abstract (arXiv)

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 f1/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 testing feasibility of a semidefinite program (of possibly large size). 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-sos-convexity and extend a result of Reznick on sum of squares representation of positive definite forms to positive definite biforms. We conclude with some applications of polynomial norms to statistics and dynamical systems.