3. Norms

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

.:VR(VRn).

An example is relative error:

xyx.

|.| is a norm if

  1. |x|0, |x|=0x=0.
  2. |αx|=|α||x|
  3. |x+y||x|+|y|. Sub-additivity / triangle inequality.

Common Vector Norms

The infinity norm is the maximum value of a vector

x=maxi|xi|.

This is very punishing of outliers.

The 1 norm is the sum of the absolute values

x1=i=0n|xi|.

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

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

(|xi|)1/p.

The limit is what happens when p.

Isometries

Isometries are operations that do not change the norms.

Norm Equivalence

Given two norms |x|a and |x|b, there is a theorem that constants c1,c2 such that

c1xbxac2xb.

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

maxi|xi|i=0n|xi|nmaxi|xi|.

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

Matrix Norms

Suppose ARm×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.

Ap=supxp=1Axp.

See 2.9. Superconvergence.

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

AvAv.ABAB.

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

[2200][1010]max=4.

Matrix Isometries

Suppose M1 and M2 are permutation matrices.

M1AM2p=maxx=1M1AM2xp.

This property also holds for frobenius norms.

Matrix 2-norm (spectral norm)

Suppose we have |A|22=max|x|1|Ax|22=xTATAx.

ATA is a symmetric matrix, so it has a full set of orthonormal vectors for its eigenvalues.

ATA=VΛVT where VTV=I.

|A|2=λmax(ATA).