Examples of norms essentially different from $p$-norms

Question

I'm looking for examples of norms that can be applied to finite-dimensional vectors but are not just $p$-norms or trivial variations of them. The ones I've found - the norms in James' space or Tsirelson's space - only make sense for infinite dimensions.

To be more precise, I'm looking for norms which are not of the form $\|v\| := \|Av\|_p$ for some positive definite matrix $A$, or $\|v\| := \lambda \|v\|_p + (1-\lambda)\|v\|_q$.

The only example I've found so far is the norm defined as $$ \|v\|^{(k)} := \sum_{i=1}^k \max_j{}^{\!(i)} |v_j|,$$ where $\max^{(i)}$ is the $i$th largest element.

There must be more interesting norms. Any ideas?

Answer 1

A norm is uniquely determined by its unit ball, and conversely, you can define a norm to have any unit ball you like. The construction goes like this. Let $K\subset \mathbb{R}^n$ be a closed, bounded, convex, and symmetric set ($x\in K$ if and only if $-x\in K$). Define

$$\|x\|_K = \inf\{\lambda > 0 \, |\, x \in \lambda K\}.$$

This is called the Minkowski functional, and $\|\cdot \|_K$ is a semi-norm. If you also assume $K$ contains an open neighborhood of the origin, then $\|\cdot \|_K$ is a norm, and the unit ball for the norm is exactly $K$.

So basically you can select any $K$ (within reason) and define a norm for which $K$ is the unit ball. Every norm can be constructed in this way, so it is very general and generates "new" norms that are not just $p$ norms.

As an example, let $X_m$ be a collection of $m$ independent and identically distributed random variables $\mathbb{R}^n$ with a Lebesgue density, and set

$$K_m = \text{ConvexHull} (-X_m \cup X_m).$$

Then define the norm $\|x\|_{K_m}$. This is a norm with a unit ball that is a random convex polytope (provided $2m \geq n+1$).

A concrete example is the $n$-dimensional polytope with vertices of the form $$\frac{1}{\sqrt k} \sum_{i=1}^k s_{\sigma(i)} e_{\sigma(i)}$$ for all $k \le n$, all signs $s$ and permutations $\sigma$. It has $\sum_{i=1}^n {n \choose i}2^i$ vertices.

Answer 2

Take any norm $\nu$ on a function space and then define $$\Vert(a_1,\ldots,a_n)\Vert=\nu\left(t\mapsto\sum_{k=1}^na_kt^{k-1}\right).$$ For example $$\Vert(a_1,\ldots,a_n)\Vert=\sup_{t\in[0,1]}\left\vert\sum_{k=1}^na_kt^{k-1}\right\vert$$ Or $$\Vert(a_1,\ldots,a_n)\Vert=\int_{0}^1\left\vert\sum_{k=1}^na_kt^{k-1}\right\vert \omega(t) dt$$ For some positive weight $\omega$.

Answer 3

I still would like to have some more "natural" examples of such norms, specifically those with smooth and permutation-symmetric unit balls. Using the Minkowski functional, as explained by Jeff, allows me to define a norm from any convex body which is closed, convex, and symmetric. Playing around I found two nice unit balls. One is

$$ K_\text{exp} = \{x \in \mathbb R^n: \frac{1}{e+n-1}\sum_{i=1}^n e^{x_i^2} \le 1\},$$ for which it is really difficult to calculate the corresponding norm $\|\cdot\|_\text{exp}$ for any non-trivial vector. The cases I could solve analytically are $$\|1^{(n)}\|_\text{exp} = \frac{1}{\sqrt{\log(1+(e-1)/n)}}$$ where $1^{(n)}$ is the vector of all ones, and for the vector $(1,\sqrt{2})$ we have $$\|(1,\sqrt{2})\|_\text{exp} = \frac{1}{\sqrt{\log(-\frac12+\frac12\sqrt{5+4e})}}.$$ The other unit ball is $$ K_\text{log} = \{x \in \mathbb R^n: \frac12\prod_{i=1}^n(1+x_i^2)\le 1\},$$ for which I also couldn't get a general formula for an arbitrary vector. For the vector of all ones we have $$\|1^{(n)}\|_\text{log} = \frac{1}{\sqrt{\sqrt[n]{2}-1}},$$ and for an arbitrary 2-dimensional vector $(x,y)$ we have $$\|(x,y)\|_\text{log} = \frac1{\sqrt2}\sqrt{x^2+y^2+\sqrt{x^4+6x^2y^2+y^4}}.$$