### May 2018

In my last blog post I wrote about Luxemburg norms which are constructions to get norms out of a non-homogeneous function ${\phi:[0,\infty[\rightarrow[0,\infty[}$ which satisfies ${\phi(0) = 0}$ and are increasing and convex (and thus, continuous). The definition of the Luxemburg norm in this case is

$\displaystyle \|x\|_{\phi} := \inf\left\{\lambda>0\ :\ \sum_{k}\phi\left(\frac{|x_{k}|}{\lambda}\right)\leq 1\right\},$

and we saw that ${\|x\|_{\phi} = c}$ if ${\sum_{k}\phi\left(\frac{|x_{k}|}{c}\right)= 1}$.

Actually, one can have a little more flexibility in the construction as one can also use different functions ${\phi}$ in each coordinate: If ${\phi_{k}}$ are functions as ${\phi}$ above, we can define

$\displaystyle \|x\|_{\phi_{k}} := \inf\left\{\lambda>0\ :\ \sum_{k}\phi_{k}\left(\frac{|x_{k}|}{\lambda}\right)\leq 1\right\},$

and it still holds that ${\|x\|_{\phi_{k}} = c}$ if and only if ${\sum_{k}\phi_{k}\left(\frac{|x_{k}|}{c}\right)= 1}$. The proof that this construction indeed gives a norm is the same as in the one in the previous post.

This construction allows, among other things, to construct norms that behave like different ${p}$-norms in different directions. Here is a simple example: In the case of ${x\in{\mathbb R}^{d}}$ we can split the variables into two groups, say the first ${k}$ variables and the last ${d-k}$ variables. The first group shall be treated with a ${p}$-norm and the second group with a ${q}$-norm. For the respective Luxemburg norm one has

$\displaystyle \|x\|:= \inf\left\{\lambda>0\ :\ \sum_{i=1}^{k}\frac{|x_{i}|^{p}}{\lambda^{p}} + \sum_{i=k+1}^{d}\frac{|x_{i}|^{q}}{\lambda^{q}}\leq 1\right\},$

Note that there is a different way to do a similar thing, namely a mixed norm defined as

$\displaystyle \|x\|_{p,q}:= \left(\sum_{i=1}^{k}|x_{i}|^{p}\right)^{1/p} + \left(\sum_{i=k+1}^{d}|x_{i}|^{q}\right)^{1/q}.$

As any two norms, these are equivalent, but they induce a different geometry. On top of that, one could in principle also consider ${\Phi}$ functionals

$\displaystyle \Phi_{p,q}(x) = \sum_{i=1}^{k}|x_{i}|^{p} + \sum_{i=k+1}^{d}|x_{i}|^{q},$

which is again something different.

A bit more general, we may consider all these three conditions for general partitions of the index sets and a different exponent for each set.

Here are some observations on the differences:

• For the Luxemburg norm the only thing that counts are the exponents (or functions ${\phi_{k}}$). If you partition the index set into two parts but give the same exponents to both, the Luxemburg norm is the same as if you would consider the two parts as just one part.
• The mixed norm is not the ${p}$-norm, even if the set the exponent to ${p}$ for every part.
• The Luxemburg norm has the flexibility to use other functionals than just the powers.
• For the mixed norms one could consider additional mixing by not just summing the norms of the different parts, which is the same as taking the ${1}$-norm of the vector of norms. Of course, other norms are possible, e.g. constructions like

$\displaystyle \left(\left(\sum_{i=1}^{k}|x_{i}|^{p}\right)^{r/p} + \left(\sum_{i=k+1}^{d}|x_{i}|^{q}\right)^{r/q}\right)^{1/r}$

are also norms. (Actually, the term mixed norm is often used for the above construction with ${p=q\neq r}$.)

Here are some pictures that show the different geometry that these three functionals induce. We consider ${d=3}$ i.e., three-dimensional space, and picture the norm-balls (of level sets in the case the functionals ${\Phi}$).

• Consider the case ${k=1}$ and the first exponent to be ${p=1}$ and the second ${q=2}$. The mixed norm is

$\displaystyle \|x\|_{1,2} = |x_{1}| + \sqrt{x_{2}^{2}+x_{3}^{2}},$

the ${\Phi}$-functional is

$\displaystyle \Phi(x)_{1,2} = |x_{1}| + x_{2}^{2}+x_{3}^{2},$

and for the Luxemburg norm it holds that

$\displaystyle \|x\| = c\iff \frac{|x_{1}|}{c} + \frac{x_{2}^{2} + x_{3}^{2}}{c^{2}} = 1.$

Here are animated images of the respective level sets/norm balls for radii ${0.25, 0.5, 0.75,\dots,3}$:

You may note the different shapes of the balls of the mixed norm and the Luxemburg norm. Also, the shape of their norm balls stays the same as you scale the radius. The last observation is not true for the ${\Phi}$ functional: Different directions scale differently.

• Now consider ${k=2}$ and the same exponents. This makes the mixed norm equal to the ${1}$-norm, since

$\displaystyle \|x\|_{1,2} = |x_{1}| + |x_{2}| + \sqrt{x_{3}^{2}} = \|x\|_{1}.$

The ${\Phi}$-functional is

$\displaystyle \Phi(x)_{1,2} = |x_{1}| + |x_{2}|+x_{3}^{2},$

and for the Luxemburg norm it holds that

$\displaystyle \|x\| = c\iff \frac{|x_{1}| + |x_{2}|}{c} + \frac{x_{3}^{2}}{c^{2}} = 1.$

Here are animated images of the respective level sets/norm balls of the ${\Phi}$ functional and the Luxemburg norm for the same radii as above (I do not show the balls for the mixed norm – they are just the standard cross-polytopes/${1}$-norm balls/octahedra): Again note how the Luxemburg ball keeps its shape while the level sets of the ${\Phi}$-functional changes shape while scaling.

• Now we consider three different exponents: ${p_{1}=1}$, ${p_{2} = 2}$ and ${p_{3} = 3}$. The mixed norm is again the ${1}$-norm. The ${\Phi}$-functional is

$\displaystyle \Phi(x)_{1,2} = |x_{1}| + x_{2}^{2}+|x_{3}|^{3},$

and for the Luxemburg norm it holds that

$\displaystyle \|x\| = c\iff \frac{|x_{1}|}{c} + \frac{x_{2}^{2}}{c^{2}} + \frac{|x_{3}|^{3}}{c^{3}} = 1.$

Here are animated images of the respective level sets/norm balls of the ${\Phi}$ functional and the Luxemburg norm for the same radii as above (again, the balls for the mixed norm are just the standard cross-polytopes/${1}$-norm balls/octahedra):

A function ${\phi:[0,\infty[\rightarrow[0,\infty[}$ is called ${p}$-homogeneous, if for any ${t>0}$ it holds that ${\phi(tx) = t^{p}\phi(x)}$. This implies that ${\phi(x) = x^{p}\phi(1)}$ and thus, all ${p}$-homogeneous functions on the positive reals are just multiples of powers of ${p}$. If you have such a power of ${p}$ you can form the ${p}$-norm

$\displaystyle \|x\|_{p} = \left(\sum_{k}|x_{k}|^{p}\right)^{1/p}.$

By Minkowski’s inequality, this in indeed a norm for ${p\geq 1}$.

If we have just some function ${\phi:[0,\infty[\rightarrow[0,\infty[}$ that is not homogeneous, we could still try to do a similar thing and consider

$\displaystyle \phi^{-1}\left(\sum_{k}\phi(|x_{k}|)\right).$

It is easy to see that one needs ${\phi(0)=0}$ and ${\phi}$ increasing and invertible to have any chance that this expression can be a norm. However, one usually does not get positive homogeneity of the expression, i.e. in general

$\displaystyle \phi^{-1}\left(\sum_{k}\phi(t|x_{k}|)\right)\neq t \phi^{-1}\left(\sum_{k}\phi(|x_{k}|)\right).$

A construction that helps in this situation is the Luxemburg-norm. The definition is as follows:

Definition 1 (and lemma). Let ${\phi:[0,\infty[\rightarrow[0,\infty[}$ fulfill ${\phi(0)=0}$, ${\phi}$ be increasing and convex. Then we define the Luxemburg norm for ${\phi}$ as

$\displaystyle \|x\|_{\phi} := \inf\{\lambda>0\ :\ \sum_{k}\phi\left(\frac{|x_{k}|}{\lambda}\right)\leq 1\}.$

Let’s check if this really is a norm. To do so we make the following observation:

Lemma 2 If ${x\neq 0}$, then ${c = \|x\|_{\phi}}$ if and only if ${\sum_{k}\phi\left(\frac{|x_{k}|}{c}\right) = 1}$.

Proof: Basically follows by continuity of ${\phi}$ from the fact that for ${\lambda >c}$ we have ${\sum_{k}\phi\left(\frac{|x_{k}|}{\lambda}\right) \leq 1}$ and for ${\lambda we have ${\sum_{k}\phi\left(\frac{|x_{k}|}{\lambda}\right) > 1}$. $\Box$

Lemma 3 ${\|x\|_{\phi}}$ is a norm on ${{\mathbb R}^{d}}$.

Proof: For ${x=0}$ we easily see that ${\|x\|_{\phi}=0}$ (since ${\phi(0)=0}$). Conversely, if ${\|x\|_{\phi}=0}$, then ${\limsup_{\lambda\rightarrow 0}\sum_{k}\phi\left(\tfrac{|x_{k}|}{\lambda}\right) \leq 1}$ but since ${\lim_{t\rightarrow\infty}\phi(t) = \infty}$ this can only hold if ${x_{1}=\cdots=x_{d}= 0}$. For positive homogeneity observe

$\displaystyle \begin{array}{rcl} \|tx\|_{\phi} & = & \inf\{\lambda>0\ :\ \sum_{k}\phi\left(\frac{|tx_{k}|}{\lambda}\right)\leq 1\}\\ & = & \inf\{|t|\mu>0\ :\ \sum_{k}\phi\left(\frac{|x_{k}|}{\mu}\right)\leq 1\}\\ & = & |t|\|x\|_{\phi}. \end{array}$

For the triangle inequality let ${c = \|x\|_{\phi}}$ and ${d = \|y\|_{\phi}}$ (which implies that ${\sum_{k}\phi\left(\tfrac{|x_{k}|}{c}\right)\leq 1}$ and ${\sum_{k}\phi\left(\tfrac{|y_{k}|}{d}\right)\leq 1}$). Then it follows

$\displaystyle \begin{array}{rcl} \sum_{k}\phi\left(\tfrac{|x_{k}+y_{k}|}{c+d}\right) &\leq& \sum_{k}\phi\left(\tfrac{c}{c+d}\tfrac{|x_{k}|}{c} +\tfrac{d}{c+d}\tfrac{|y_{k}|}{d}\right)\\ &\leq& \tfrac{c}{c+d}\underbrace{\sum_{k} \phi\left(\tfrac{|x_{k}|}{c}\right)}_{\leq 1} + \tfrac{d}{c+d}\underbrace{\sum_{k}\phi\left(\tfrac{|y_{k}|}{d}\right)}_{\leq 1}\\ &\leq& 1 \end{array}$

and this implies that ${c+d \geq \|x+y\|_{\phi}}$ as desired. $\Box$

As a simple exercise you can convince yourself that ${\phi(t) = t^{p}}$ lead to ${\|x\|_{\phi} = \|x\|_{p}}$.

Let us see how the Luxemburg norm looks for other functions.

Example 1 Let ‘s take ${\phi(t) = \exp(t)-1}$.

The function ${\phi}$ fulfills the conditions we need and here are the level lines of the functional ${x\mapsto \phi^{-1}\left(\sum_{k}\phi(|x_{k}|)\right)}$ (which is not a norm):

[Levels are ${0.5, 1, 2, 3}$]

The picture shows that this functional is not a norm ad the shape of the “norm-balls” changes with the size. In contrast to that, the level lines of the respective Luxemburg norm look like this:

[Levels are ${0.5, 1, 2, 3}$]