CAL1_L1

Preliminaries

Recall what a normed vector space is. We say that $V$ is a complete normed linear space if $(V,\Vert \cdot \Vert )$ is a complete metric space with respect to the metric induced by the norm.

Equivalence of norms

Definition 1(Definition).

Let $V$ be a normed linear space with respect to two norms $\Vert \cdot {\Vert }^{\times }$ and $\Vert \cdot {\Vert }^{\circ }$. We say that the two norms are equivalent if there exist $c_1,c_2\in \mathbb{R}$ such that

$$c_1\Vert \cdot {\Vert }^{\times }\le \Vert \cdot {\Vert }^{\circ }\le c_2\Vert \cdot {\Vert }^{\times }.$$

An aside

Two metrics $\rho$ and $\sigma$ on a set $X$ are said to be equivalent if there exist positive numbers $c_1$ and $c_2$ such that for all $x_1,x_2\in X$,

$$c_1\sigma (x_1,x_2)\le \rho (x_1,x_2)\le c_2\sigma (x_1,x_2).$$

It can be shown that a subset of $X$ is open in the metric space $(X,\rho )$ if and only if it is open in $(X,\sigma )$.

Note that if two norms are equivalent, the metrics induced by them are also equivalent for the same $c_1$ and $c_2$.

The p-norm

The p-norm generalizes the euclidean norm in ${\mathbb{R}}^n$.

Definition 2(Definition).

For $1\le p\le \infty$ and $\mathbf{x}\in {\mathbb{R}}^n$,

$$\begin{array}{r}\Vert \mathbf{x}{\Vert }_p={\left(\sum _{i=1}^n|x_i{|}^p\right)}^{1/p}\end{array}$$

Notice that for $p=\infty$, $\Vert \mathbf{x}{\Vert }_{\infty }=\max \{|x_i|\}$.

All the properties except the triangle inequality are trivial to show. The only non trivial property that needs to be proved is the triangle inequality.

Theorem 3(Claim).

The p-norm satisfies the triangle inequality, i.e,

$${\left(\sum |x_i+y_i{|}^p\right)}^{1/p}\le {\left(\sum |x_i{|}^p\right)}^{1/p}+{\left(\sum |y_i{|}^p\right)}^{1/p}$$

Proof
If $p=1$, the claim follows from the triangle inequality in $\mathbb{R}$. For $1<p$, we have

$$\begin{array}{rl}\sum |x_i+y_i{|}^p& =\sum |x_i+y_i{|}^{p-1}|x_i+y_i|\\ & \le \sum |x_i+y_i{|}^{p-1}|x_i|+\sum |x_i+y_i{|}^{p-1}|y_i|\end{array}$$

Applying Holder’s inequality ($\frac{1}{q}\equiv 1-\frac{1}{p}$), we get

$$\begin{array}{rlr}\sum |x_i+y_i{|}^p\le & {\left(\sum |x_i{|}^p\right)}^{1/p}{\left(\sum |x_i+y_i{|}^{(p-1)q}\right)}^{1/q}+& \\ & {\left(\sum |y_i{|}^p\right)}^{1/p}{\left(\sum |x_i+y_i{|}^{(p-1)q}\right)}^{1/q}& \\ ⟹{\left(\sum |x_i+y_i{|}^p\right)}^{1/p}\le & {\left(\sum |x_i{|}^p\right)}^{1/p}+{\left(\sum |y_i{|}^p\right)}^{1/p}& (p-1)q=p\end{array}$$

◻️

Quick exercise: verify the triangle inequality for the infinity norm.