# 3. Norms

A norm is how we measure the length/size of vectors and matrices.

$\| . \|: V\to \R\quad (V \subset \R^n).$

An example is relative error:

$\frac{\|x-y\|}{\|x\|}.$

$|.|$ is a norm if

1. $|x| \geq 0$, $|x| = 0 \iff x=0$.
2. $| \alpha x|= |\alpha| |x|$
3. $|x+y| \leq |x| + |y|$. Sub-additivity / triangle inequality.

## Common Vector Norms

The infinity norm is the maximum value of a vector

$\|\vec x\|_\infty =\max_i|x_i|.$

This is very punishing of outliers.

The 1 norm is the sum of the absolute values

$\|x\|_1 = \sum_{i=0}^n|x_i|.$

The 2 norm is the square root of sum the squares.

These are all examples of $p$-norms, which are given by

$\Bigg(\sum|x_i|\Bigg)^{1/p}.$

The limit is what happens when $p\to \infty$.

## Isometries

Isometries are operations that do not change the norms.

• Permutations
• $|Px|_p =|x|_p$.
• Orthogonal matrices
• $|Qx|_2^2 = x^TQ^TQx = x^Tx = |x|_2^2$.

## Norm Equivalence

Given two norms $|x|_a$ and $|x|_b$, there is a theorem that $\exists$ constants $c_1, c_2$ such that

$c_1\|x\|_b \leq \|x\|_a \leq c_2\|x\|_b.$

Example. The infinity norm is less than the 1 norm less than $n$ times the infinity norm.

$\max_i|x_i| \leq \sum_{i=0}^n|x_i|\leq n \max_i|x_i|.$

Note that they are equivalent when $x$ has exactly 1 non-zero element or all the entries are 0.

## Matrix Norms

Suppose $A \in \R^{m\times n}$. The Frobenius norm is treating a matrix as a $mn$ dimension vector and taking the 2-norm.

We can also calculate the induced norm, or operator norm.

$\|A\|_p = \sup_{\|x\|_p = 1} {\|Ax\|_p}.$

A nice property of induced norms is that they are subordinate and submultiplicative. See Cauchy-Schwarz. 1.4. Geometry of the real numbers.

$\|Av\|\leq \|A\|\|v\|.\\ \|AB\|\leq \|A\|\|B\|.$

This is not a property of all norms. For example, suppose we want ot take the max norm

$\Bigg\|\begin{bmatrix}2&2\\0&0\end{bmatrix}\begin{bmatrix}1&0\\1&0\end{bmatrix}\Bigg \|_{max} = 4.$

### Matrix Isometries

Suppose $M_1$ and $M_2$ are permutation matrices.

$\|M_1AM_2\|_p = \max_{\|x\|=1}\|M_1AM_2x\|_p.$

This property also holds for frobenius norms.

### Matrix 2-norm (spectral norm)

Suppose we have $|A|^2_2=\max_{|x|_1} |Ax|^2_2 = x^TA^TAx$.

$A^TA$ is a symmetric matrix, so it has a full set of orthonormal vectors for its eigenvalues.

$A^TA = V\Lambda V^T$ where $V^TV = I$.

$|A|_2 = \sqrt{\lambda_{max} (A^TA)}$.