Norm

Norm and Unit Ball

A norm $\Vert \cdot \Vert:\mathbb{R}^n \rightarrow \mathbb{R}$ is a function that satisfies the following properties:

1. Positive definite: $\Vert x \Vert = 0 \rightarrow x = \vec 0$,

2. Nonnegative:$\Vert x \Vert \ge 0$ for any $x \in \mathbb{R}^n$,

3. Absolutely homogeneous: $\Vert k x\Vert = |k| \cdot \Vert x \Vert$, for any $x \in \mathbb{R}^n, k \in \mathbb{R}$,

4. Subadditive (triangle inequality): $\Vert x + y \Vert \le \Vert x \Vert + \Vert y \Vert$, for any $x \in \mathbb{R}^n, y \in \mathbb{R}^n$.

Theorem. Given properties 1-3, property 4 is equivalent to

5. The region $\{ x \in \mathbb{R}^n: \Vert x \Vert \le 1\}$ is convex.

Proof. The proof is straightforward.

$5 \rightarrow 4:$ If $x = \vec 0$ or $\vec y = 0$, then 4 holds trivially. Otherwise, suppose that $x, y \neq \vec 0$. Then

As $\left\Vert \frac{ x }{ \Vert x \Vert } \right\Vert =1$, $\left\Vert \frac{ y }{ \Vert y \Vert } \right\Vert = 1$ and $\frac{ \Vert x \Vert }{ \Vert x \Vert + \Vert y \Vert } + \frac{ \Vert y \Vert }{ \Vert x \Vert + \Vert y \Vert } = 1$, the second inequality follows exactly from condition 5.

$4 \rightarrow 5:$ Let $x, y \in \mathbb{R}^n, \Vert x \Vert \le 1, \Vert y \Vert \le 1$ and $a, b \ge 0$, $a + b = 1$. Then

$\square$

Induced Norm

To illustrate a deeper connection between property 4 and 5, we first show how a norm can be induced by a convex and symmetric region centered at the origin $O$. Let the boundary of the region as $E$. We are going to induce a norm by $E$, denoted as $\Vert \cdot \Vert_E$.

First, we define

1. $\Vert x \Vert_E = 1, \forall x \in E$.

For any other vector $x \notin E$, consider the ray initiated from the origin and with the same direction as $x$. Denote its intersection point with $E$ as $x_E$. Suppose that $x = a \cdot x_E$ for some $a \in \mathbb{R}_+$. Then we define

2. $\Vert x \Vert_E = a \Vert x_E \Vert_E = a$.

Indeed, if we write the $\Vert \cdot \Vert_2$ as the $\ell_2$ norm, then the value of $a$ is given by $\frac{ \Vert x \Vert_2 } { \Vert x_E \Vert_2 }$. Clearly, by definition, $\Vert \cdot \Vert_2$ is positive definite and non-negative. To prove that it is absolutely homogeneous, $\forall k \in \mathbb{R}$,

If $k \ge 0$, we have $\Vert k ax_E\Vert_E = ka \Vert x_E \Vert_E = ka$. Otherwise, if $k < 0$,

By symmetry of $E$ (with respect to the origin $O$), $\Vert (-x_E)\Vert_E = \Vert x_E \Vert_E = 1$. Therefore,

Finally, we have a graphical verification of triangle inequality. Let $v, u \in \mathbb{R}^n$, which intersect with $E$ at $v_E$ and $u_E$ respectively. If $\Vert v\Vert_E < 1$ ($\Vert u\Vert_E < 1$), then we can extend it along its direction to get its intersection with $E$. Let $c = \Vert v\Vert_E$ and $d = \Vert u \Vert_E$, then

1. $v = c \cdot v_E$,
2. $u = d \cdot u_E$.

Let $w = v + u = c \cdot v_E + d \cdot u_E$. Let $p$ be the intersection between $w$ and the line segment between $v$ and $u$. It is easy to verify that

By convexity of the region bounded by $E$,

It concludes that $\Vert w\Vert_E = \Vert c v_E + d u_E \Vert_E \le c + d = \Vert v\Vert_E + \Vert u \Vert_E$.

Application

The idea discussed above significantly simplifies the proof of Minkowski inequality.

The $p$-norm ($p \ge 1$) on $\mathbb{R}^n$ is given as

Clearly, $p$-norm is positive definite, nonnegative, absolutely homogeneous. It is left to verify triangle inequality, which is known as Minkowski inequality for the case of $p$-norm. This is equivalent to show that

is convex. The trick here is that $\Vert x \Vert_p \le 1$ is equivalent to $(\Vert x \Vert_p)^p \le 1$. Hence,

The convexity of this set follows directly from the point-wise convexity of the function $f(t) = t^p$.

$\square$

Remark: To appreciate how concise the above proof is, we also give one traditional proof here, which consists of three steps.

Young's Inequality

Theorem. For $a, b > 0$, $p, q > 0$, s.t., $\frac{1}{p} + \frac{1}{q} = 1$, it holds that

$$ab \le \frac{a^p}{p} + \frac{b^q}{q}$$

Proof. Via the concavity of $y = \ln x, x > 0$, we see

$\square$

Holder's Inequality

Theorem. For $x, y \in \mathbb{R}^n$, $p, q > 0$, s.t., $\frac{1}{p} + \frac{1}{q} = 1$, it holds that

$$\sum_{i \in [n]} |x_i| |y_i| \le \Vert x \Vert_p \Vert y \Vert_q$$

Proof. The inequality is trivial if $x = \vec 0$ or $y = \vec 0$. Otherwise, let $u = x / \Vert x \Vert_p$ and $v = y / \Vert y \Vert_q$. It is easy to see that $\Vert u \Vert_p = \Vert v \Vert_q = 1$, and it remains to prove

Applying Young's Inequality, we have

$\square$

Minkowski Inequality

For $x, y \in \mathbb{R}^n$, $p \ge 1$, it holds that

$$\Vert x + y \Vert_p \le \Vert x \Vert_p + \Vert y \Vert_p$$

Proof. The inequality is trivial if $x = \vec 0$ or $y = \vec 0$. Otherwise, assume that $x > 0$ and $y > 0$. Now

Let $q = \frac{p}{p - 1}$. Then $\frac{1}{p} + \frac{1}{q} = 1$. By Holder's inequality,

Similarly, we have

Putting the inequalities together,

We finish the proof by dividing both side with $(\Vert x + y \Vert_p)^{p - 1}$.

$\square$