1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Have you considered the various matrix norms? Matrices are finite-dimensional vectors, after all. $\endgroup$ – Wouter Feb 28 '18 at 12:04
  • $\begingroup$ Yes, I have. But to get an interesting matrix norm you'd need to reshape the vector into a rectangular matrix, which will only work if the dimension is not a prime number, or if you pad the vector with zeroes until the dimension is nice. I was hoping for something less contrived. $\endgroup$ – Mateus Araújo Feb 28 '18 at 13:18
5
+100
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ Can you add a concrete example of an interesting $K$? $\endgroup$ – Mateus Araújo Mar 1 '18 at 12:52
  • $\begingroup$ There are an infinity of possible examples; I don't know what you find interesting. I added an example where the unit ball is a random polytope. $\endgroup$ – Jeff Mar 1 '18 at 14:58
  • $\begingroup$ Yes, there is an infinity of possible examples, this is exactly the problem. "Interesting" is left for you to decide, but I had something more concrete in mind than a random polytope. $\endgroup$ – Mateus Araújo Mar 1 '18 at 15:30
  • 1
    $\begingroup$ @MateusAraújo Jeff answered exactly your question as it was formulated above. Even more, he gave you a tool to find all norms. Which are "essentially different" or "interesting" is up to you. Almost all norms described this way are unlike the $p$-norms, e.g. taking as unit circle a regular polygon on even many sides. Either you edit the question or you post a new qustion with your actual restriction. Because I see no way to answer this one other than Jeff did. $\endgroup$ – M. Winter Mar 4 '18 at 2:00
  • 1
    $\begingroup$ I suppose then you do not consider $\|x\|_p:= (\sum |x_i|^p)^{1/p}$ an example of a norm until it is instantiated by choosing a value for $p$? $\endgroup$ – Jeff Mar 4 '18 at 19:50
2
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ I haven't done a proof, but I'm pretty sure both your examples reduce to $\|v\|=\|Av\|_p$ for some positive definite matrix $A$. $\endgroup$ – Mateus Araújo Mar 1 '18 at 13:25
  • $\begingroup$ I doubt this is the case, especially with the first example where $\nu$ is arbitrary. $\endgroup$ – Jeff Mar 1 '18 at 15:51
  • $\begingroup$ I think you missed the "both of your examples" part of my sentence. $\endgroup$ – Mateus Araújo Mar 1 '18 at 16:02
  • $\begingroup$ I still doubt either example is in the form you suggested. If you think it is, give a proof. $\endgroup$ – Jeff Mar 1 '18 at 16:09
  • $\begingroup$ Well, Felix Klein is the one proposing this as an example of a norm which is not of the undesired form, I think the burden of proof lies with him. $\endgroup$ – Mateus Araújo Mar 1 '18 at 17:07
0
$\begingroup$

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}}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.