Matrix computations &
Numerical linear algebra

David Gleich

Purdue University

Fall 2012

Course number CS-51500

Tuesday and Thursday, 10:30-11:45am

Location Lawson 1106

Vector norms

$\newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\tvec}{vec} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

These notes introduce vector norms and discuss their properties.

Rationale for a vector norm

The idea with a vector norm is a to measure the size of a vector with reference to the $0$ vector. Such a norm also provides us with a distance measure between vectors, which let us answer questions such as: is $\vx$ close to $\vy$?

Definition of a vector norm

Let $\vx, \vy \in \RR^{n}$, and $\alpha \in \RR$. A function $f$ that satisfies the following three properties is called a vector norm:

1. $f(\vx) \ge 0$ and $f(\vx) = 0$ only when $\vx = 0$.
2. $f(\vx + \vy) \le f(\vx) + f(\vy)$
3. $f(\alpha \vx) = |\alpha| f(\vx)$.

In such cases, we write

$$f(\vx) = \normof{\vx}.$$

The Euclidean norm

The most common vector norm is, by far, the Euclidean norm, also called the 2 norm:

$$\normof{\vx} = \normof{\vx}_2 = \sqrt{\sum_{i=1}^n |x_i|^2}.$$

Usually, this is the norm that people refer to when they aren’t specific about another choice.

The p-norms

A more general norm is the $p$-norm ($p > 1$):

$$\normof{\vx}_p = \left( \sum_{i=1}^n |x_i|^p \right)^{1/p}.$$

This becomes the Euclidean norm when $p=2$, hence, when it is also called the 2-norm. There are two other common choices:

$$p = 1 \quad : \quad \normof{\vx}_1 = \sum_{i=1}^n |x_i|$$ $$p = \infty \quad : \quad \normof{\vx}_{\infty} = \max_{1 \le i \le n} |x_i|$$

A more interesting norm

The above norms are commonly used. A less common norm is:

$$\normof{\vx}_k = \text{ sum of the $k$th largest magnitude entries in $\vx$. }$$

Note that for $k=1$, this is the $\infty$-norm defined above, just the largest magnittude entry, and for $k=n$, this is the $1$-norm.

Equivalence of norms

Does it matter which norm you use? The following theorem helps us understand that something that is small in one norm cannot be arbitrarily large in another.

THEOREM (Equivalence of Norms) Let $\normof{\vx}_a$ and $\normof{\vx}_b$ be any two vector norms on $\RR^n$. Then there exist fixed constants $c_1$ and $c_2$ such that

$$c_1 \normof{\vx}_a \le \normof{\vx}_b \le c_2 \normof{\vx}_a,$$

which hold for any $\vx \in \RR^{n}$.

Example

$$\normof{\vx}_2 \le \normof{\vx}_1 \le \sqrt{n} \normof{\vx}_2$$ $$\normof{\vx}_{\infty} \le \normof{\vx}_2 \le \sqrt{n} \normof{\vx}_{\infty}$$ $$\normof{\vx}_{\infty} \le \normof{\vx}_1 \le n \normof{\vx}_{\infty}$$

Vector convergence The importance of this theorem is given by the following definition. Let $\vx\itn{1}, \vx\itn{2}, \ldots$ be a sequence of vectors. We say that $\vx\itn{k}$ converges to $\vx$ if

$$\lim_{k\to\infty} \normof{\vx\itn{k} - \vx} = 0.$$

Because of the equivalcence of norms, we can show this result for any vector norm. For the forthcoming problems with PageRank, showing such results with the 1-norm will be especially nice.

A small digression
Many people call these norms the $\ell_1, \ell_2,$ and $\ell_{\infty}$ norms, or even the $L_1, L_2$, and $L_{\infty}$ norms. In my view, these are misnomers, although, they aren’t incorrect. Usually the $\ell_1$ and $L_1$ norms apply to sequences and functions, respectively:
$\ell_1 : \sum_{i=1}^\infty |x_i|$
$L_1 : \int_{D} |f| \, d\mu$ (over an appropriately measureable space.) So I prefer 1-norm, 2-norm, and $\infty$-norm to the “L” versions.