Norms

A function $\|\cdot\|: \mathbb{C}^m \rightarrow \mathbb{R}$ is a norm iff:

• (Nonnegativity) $\|x\| \geq 0$, $\|x\| = 0 \Leftrightarrow x = 0$
• (Triangle Inequality) $\|x+y\| \leq \|x\| + \| y \|$
• (Scaling) $\|\alpha x\| = |\alpha|\|x\|$ for a scalar $\alpha$,

Vector Norms

The Euclidian $\ell_2$ norm

\begin{eqnarray} \|x\|_2 & = & \left(x_1^2 + x_2^2 + \dots + x_N^2\right)^{\frac{1}{2}} \end{eqnarray}

Often denoted as $\|x\|$.

The $\ell_1$ and $\max$-norms

Other norms are: \begin{eqnarray} \|x\|_1 & = & \left|x_1\right| + \left|x_2\right| + \dots + \left|x_N\right| \end{eqnarray}

\begin{eqnarray} \|x\|_\infty & = & \max\{\left|x_1\right|,\left|x_2\right|,\dots,\left|x_N\right|\} \end{eqnarray}

$p$-norm

and more general $p$ norms \begin{eqnarray} \|x\|_p & = & \left( \left|x_1\right|^p + \left|x_2\right|^p + \dots + \left|x_2\right|^p\right)^{\frac{1}{p}} \end{eqnarray}

Norm Balls

Given a $p \geq 1$, a $p$-norm ball is the set of points $$ B_p = \{ x : \| x \|_p \leq 1 \} $$

Weighted norms

For an arbitrary nonsingular matrix $W$,

$$ \|x\|_W = \|Wx\| $$

The Matrix norm

Matrix Norm:

• (Nonnegativity) $\|A\| \geq 0$, $\|A\| = 0 \Leftrightarrow A = 0$
• (Triangle Inequality) $\|A+B\| \leq \|A\| + \| B \|$
• (Scaling) $\|\alpha A\| = |\alpha|\|A\|$ for a scalar $\alpha$,

\begin{eqnarray} \|A\|_{(p,q)} = \sup_{\|x\|\neq 0} \frac{\|A x\|_{(p)}}{\|x\|_{(q)}} = \sup_{\|x\|_{(q)} = 1} {\|A x\|_{(p)}} \end{eqnarray}

This is the maximum $p$-norm of the vector $Ax$ where $x$ is an element of the unit $q$-norm-ball.

Below, we show the image $Y$ of a set of points on the unit $q$-norm ball, i.e. $Y = \{y : y = Ax; \|x\|_q = 1 \}$. The dotted lines are the points that have $\|y\|_p = r$.

Given the image, what can you say about $\|A\|_{(p,q)}$ ?

Frobenius Norm

$\|A\|_F = \sqrt{Tr(A^\top A)}$

We show that the function $\|A\|_F$ is a norm:

Nonegativity and Scaling are obvious. The triangle inequality is:

\begin{eqnarray} \|A + B \|_F^2 & = & Tr((A + B)^\top (A + B) ) \\ & = & Tr(A^\top A + B^\top B + A^\top B + B^\top A) \\ & = & Tr(A^\top A) + Tr(B^\top B) + 2 Tr(B^\top A) \\ & = & \|A\|_F^2 + \|B\|_F^2 + 2 Tr(B^\top A) \\ & \leq & \|A\|_F^2 + \|B\|_F^2 + 2 |Tr(B^\top A)| \\ & \leq & \|A\|_F^2 + \|B\|_F^2 + 2 \|A\|_F \|B\|_F \\ & = & (\|A\|_F + \| B \|_F)^2 \end{eqnarray}

Cauchy-Schwarz for the Frobenius norm \begin{eqnarray} |Tr(B^\top A)| \leq \|A\|_F \|B\|_F \end{eqnarray} holds as \begin{eqnarray} Tr(B^\top A) & = & vec(B)^\top vec(A) \\ \|A\|_F & = & \|vec(A)\|_2 \end{eqnarray}

Let $C = AB$. Hence, $c_{i,j} = a_i^\top b_j$ where $a_i^\top$ is the $i$'th row of $A$ and $b_j$ is the $j$'th column of $B$

\begin{eqnarray} \| A B \|_F^2 & = & \sum_{i} \sum_j |c_{i,j} |^2 \\ & = & \sum_{i} \sum_j |a^\top_{i} b_j |^2 \\ & \leq & \sum_{i} \sum_j \|a_i\|^2 \|b_j\|^2 \\ & = & \left(\sum_{i} \|a_i\|^2 \right) \left(\sum_j \|b_j\|^2 \right)\\ & = & \| A \|_F^2 \| B \|_F^2 \\ \end{eqnarray}

Hence $$ \| A B \|_F \leq \| A \|_F \| B \|_F $$

Drawing norm-balls in 2-D

Calculate the points in polar coordinates.

In $2$D, take rays of the form $$x = \left( \begin{array}{c} x_1 \\ x_2 \end{array} \right) = \left( \begin{array}{c} \alpha \cos(\theta) \\ \alpha \sin(\theta) \end{array} \right) $$ where $\alpha>0$ and $0\leq \theta \leq 2\pi$.

The $p$-norm of a vector $x$ with $\|x\|_p = 1 $ satisfies

$\left|x_1\right|^p + \left|x_2\right|^p = \alpha^p (\left|\cos(\theta)\right|^p + \left|\sin(\theta)\right|^p) = 1 $

Solve for $\alpha(\theta)$: $$\alpha = \left(\frac{1}{\left|\cos(\theta)\right|^p + \left|\sin(\theta)\right|^p}\right)^{1/p} $$

3.1

Prove that $\|x\|_W = \|Wx\|$ is a norm for any nonsingular matrix.

• Nonnegativity $\|x\|_W \geq 0$, $\|x\|_W = 0$ iff $x=0$.

$\|x\|_W $ is nonnegative as $\|\cdot\|$ is.

Assume $x\neq 0$ and $$ Wx = 0 $$. But as $W$ is nonsingular we have $x = W^{-1} 0 = 0$, that leads to a contradiction.

• Scaling

$$ \|\alpha x\|_W = \|\alpha Wx\| = \left|\alpha\right| \|Wx\| = \left|\alpha\right|\| x\|_W $$

• Triangle Inequality

$$ \|\ x+ y \|_W = \|Wx+Wy\| \leq \|Wx\| + \|Wy\| = \|x\|_W + \|y\|_W $$

3.3

$$ \|x\|_\infty \leq \|x\|_2 $$$$ \|x\|_2 \leq \sqrt{2} \|x\|_\infty $$

3.4

Let $B$ be a submatrix of $A$.

• How can we choose $E_r$ and $E_c$ to write $B = E_r A E_c$
• Show that $\|B\| \leq \|A\|$

3.6

Dual norm $\|x\|' = \sup_{\|y\|=1} \left| y^* x \right| $