Vector norms

In general, the ``size'' of a given variable $x$ can be represented by its norm $\vert\vert x\vert\vert$. Moreover, the distance between two variables $x$ and $y$ can be represented by the norm of their difference $\vert\vert x-y\vert\vert$. In other words, the norm of $x$ is its distance to the origin $y=0$ of the space in which $x$ exists.

Specifically, the norm $\vert\vert x\vert\vert$ is defined according to the space in which the variable $x$ exists:

• In 1-D real axis, the norm of a real number $x\in \mathbb{R}$ is its absolute value $\vert x\vert$, its distance to the origin.
• In 2-D complex plane, the norm of a complex number $z=x+jy\in\mathbb{C}$ is its modulus $\vert z\vert=\sqrt{x^2+y^2}$, its Euclidean distance to the origin.
• In N-D space ($N\ge 3$), the norm of a vector ${\bf x}=[x_1,\cdots,x_N]^T$ can be defined as its Euclidean distance to the origin of the space.

The concept of norm can also be generalized to other forms of variables, such a function $f(t)$, and an $M\times N$ matrix ${\bf A}$.

Although vector norm is generally defined as $\vert\vert{\bf x}\vert\vert=\sqrt{\langle{\bf x},{\bf x}\rangle}$, other alternative forms of norm are also widely used to measure the size of a vector.

Definition

The norm of a vector ${\bf x} \in V$ in vector space $V$ is a real non-negative value representing intuitively the length, size, or magnitude of the vector. Specifically, the norm of ${\bf x} \in V$ must satisfy the following three conditions:

• Positivity:
  
  $$\vert\vert{\bf x}\vert\vert\ge 0,\;\;\;\;\;\;\vert\vert{\bf x}\vert\vert=0 \;\;\;\mbox{iff}\;\;\;{\bf x}={\bf0}$$
  
  

• Homogeneity:
  
  $$\vert\vert a{\bf x}\vert\vert=\vert a\vert\;\vert\vert{\bf x}\vert\vert,\;\;\;\;\;\;a\in R\;\;\;\mbox{or}\;\;\;C$$
  
  

• Triangle inequality:
  
  $$\vert\vert{\bf x}+{\bf y}\vert\vert\le \vert\vert{\bf x}\vert\vert+\vert\vert{\bf y}\vert\vert$$
  
  

The triangle inequality can also be expressed in alternative forms. Replacing ${\bf y}$ by ${\bf z}=-{\bf y}$ we get

$$\vert\vert{\bf x}-{\bf z}\vert\vert\le \vert\vert{\bf x}\vert\vert+\vert\vert{\bf z}\vert\vert$$

Also, subtracting $\vert\vert{\bf y}\vert\vert$ from both sides, and defining ${\bf z}={\bf x}+{\bf y}$ (so that ${\bf x}={\bf z}-{\bf y}$), we get

$$\vert\vert{\bf z}\vert\vert-\vert\vert{\bf y}\vert\vert\le \vert\vert{\bf z}-{\bf y}\vert\vert$$

which holds for either $\vert\vert{\bf z}\vert\vert>\vert\vert{\bf y}\vert\vert$ or $\vert\vert{\bf z}\vert\vert<\vert\vert{\bf y}\vert\vert$, and can be further written as

$$\bigg\vert \vert\vert{\bf x}\vert\vert-\vert\vert{\bf y}\vert\vert\bigg\vert\le \vert\vert{\bf x}-{\bf y}\vert\vert$$

Combining the two results above, we get

$$\vert\vert{\bf x}\vert\vert-\vert\vert{\bf y}\vert\vert\le\v... ...ert\le \vert\vert{\bf x}\vert\vert+\vert\vert{\bf y}\vert\vert$$

Definition

Two norms $\vert\vert{\bf x}\vert\vert _a$ and $\vert\vert{\bf x}\vert\vert _{a'}$ are equivalent if there exist two positive real constants $c$ and $C$ so that

$$c \vert\vert{\bf A}\vert\vert _{a'}\le \vert\vert{\bf A}\vert\vert _a\le C \vert\vert{\bf A}\vert\vert _{a'}$$

Theorem

All different norms ${\bf x}$ are equivalent.

Proof

• We first show that equivalence is transitive, i.e., if both $\vert\vert{\bf x}\vert\vert$ and $\vert\vert{\bf x}\vert\vert'$ are equivalent to $\vert\vert{\bf x}\vert\vert _1$:
  
  $$c \vert\vert{\bf x}\vert\vert _1\le \vert\vert{\bf x}\vert... ...vert{\bf x}\vert\vert'\le C' \vert\vert{\bf x}\vert\vert _1,$$
  
  
  then they are equivalent to each other.

  From the first equation we get $\vert\vert{\bf x}\vert\vert _1\ge \vert\vert{\bf x}\vert\vert/C$ and $\vert\vert{\bf x}\vert\vert _1\le \vert\vert{\bf x}\vert\vert/c$, which, when substituted, respectively, into the left and right hand sides of the second equation, yield:
  

  $$\frac{c'}{C} \vert\vert{\bf x}\vert\vert\le \vert\vert{\bf x}\vert\vert'\le \frac{C'}{c} \vert\vert{\bf x}\vert\vert,$$
  
  
  indicating $\vert\vert{\bf x}\vert\vert$ and $\vert\vert{\bf x}\vert\vert'$ are indeed equivalent.

• We next show an arbitrary norm $\vert\vert{\bf x}\vert\vert$ is equivalent to $\vert\vert{\bf x}\vert\vert _1$
  
  $$c \vert\vert{\bf x}\vert\vert _1\le \vert\vert{\bf x}\vert\vert\le C \vert\vert{\bf x}\vert\vert _1$$
  
  
  This is obviously true if ${\bf x}={\bf0}$ therefore $\vert\vert{\bf x}\vert\vert=\vert\vert{\bf x}\vert\vert _1=0$. For ${\bf x}\ne {\bf0}$ and therefore $\vert\vert{\bf x}\vert\vert _1>0$, we can always normalize ${\bf x}$ to define a new vector ${\bf u}={\bf x}/\vert\vert{\bf x}\vert\vert _1$ with $\vert\vert{\bf u}\vert\vert _1=1$, so that the equation above becomes
  
  $$c\le \vert\vert{\bf u}\vert\vert\le C$$
  
  
  which is all we need to prove.

• We now prove that an arbitrary $\vert\vert{\bf x}\vert\vert$ is a continuous function of ${\bf x}$ over $\vert\vert{\bf x}\vert\vert _1$, i.e., for any $\epsilon>0$, there exists a $\delta>0$ so that
  
  $$\mbox{if}\;\;\;\vert\vert{\bf x}-{\bf x}'\vert\vert _1<\del... ...vert{\bf x}\vert\vert-\vert\vert{\bf x}'\vert\vert\le\epsilon$$
  
  
  Both ${\bf x}$ and ${\bf x}'$ can be expressed in terms of a basis $\{{\bf b}_1,\cdots,{\bf b}_n\}$ that spans the space:
  
  $${\bf x}=\sum_{i=1}^n a_i{\bf b}_i,\;\;\;\;\;\;{\bf x}'=\sum_{i=1}^n a'_i{\bf b}_i$$
  
  
  then we have
  
  $$\vert\vert{\bf x}-{\bf x}'\vert\vert=\vert\vert\sum_{i=1}^n... ...f x}-{\bf x}'\vert\vert _1\max_i\vert\vert{\bf b}_i\vert\vert$$
  
  
  Now consider the alternative form of the triangle inequality of $\vert\vert{\bf x}\vert\vert$:
  
  $$\vert\vert{\bf x}\vert\vert-\vert\vert{\bf x}'\vert\vert \l... ...f x}-{\bf x}'\vert\vert _1\max_i\vert\vert{\bf b}_i\vert\vert$$
  
  
  If we let $\max_i\vert\vert{\bf b}_i\vert\vert=\epsilon/\delta$, the above becomes
  
  $$\vert\vert{\bf x}\vert\vert-\vert\vert{\bf x}'\vert\vert \le\vert\vert{\bf x}-{\bf x}'\vert\vert _1\frac{\epsilon}{\delta}$$
  
  
  indicating that for any given $\epsilon$, we can choose $\delta=\epsilon/\max_i\vert\vert{\bf b}_i\vert\vert$ so that if $\vert\vert{\bf x}-{\bf x}'\vert\vert _1\le\delta$, then $\vert\vert{\bf x}\vert\vert-\vert\vert{\bf x}'\vert\vert \le \epsilon$, i.e., the norm $\vert\vert{\bf x}\vert\vert$ is indeed continuous over $\vert\vert{\bf x}\vert\vert _1$.

• Finally, according to the extreme value theorem, a continuous function, such as $\vert\vert{\bf x}\vert\vert$, defined over a compact (closed and bounded) set, such as the unit sphere $\vert\vert{\bf u}\vert\vert _1=1$ in the n-D space, must have its maximum and minimum values:
  
  $$c=\min_{\vert\vert{\bf u}\vert\vert _1=1}\vert\vert{\bf u}\... ...{\vert\vert{\bf u}\vert\vert _1=1}\vert\vert{\bf u}\vert\vert$$
  
  
  i.e., $c\le \vert\vert{\bf u}\vert\vert\le C$, which is what we need to prove.

Q.E.D.

Here are some examples of common vector norms:

• If the vector ${\bf x}=x\in \mathbb{R}$ is a real number, then its norm is simply its absolute value $\vert\vert{\bf x}\vert\vert=\vert x\vert$.

• If the vector ${\bf z}=z=x+j y\in \mathbb{C}$ is a complex number, then its norm is simply its modulus $\vert\vert{\bf z}\vert\vert=\vert z\vert=\sqrt{x^2+y^2}$.

• If ${\bf x}=[x_1,\cdots,x_n]^T$ is a vector in an n-D vector space $V=\mathbb{R}^n$ or $V=\mathbb{C}^n$, then we can use the p-norms defined as
  
  $$\vert\vert{\bf x}\vert\vert _p=\left(\sum_{i=1}^N \vert x_i\vert^p\right)^{1/p}, \;\;\;\;\;\; 1\le p \le \infty$$
  
  
  The p-norm so defined satisfies the three requirements in the definition of the vector norm. The first two are trivially obvious, while the third one happens to be Minkowski's inequality (see appendix):
  
  $$\vert\vert{\bf x}+{\bf y}\vert\vert _p\le \vert\vert{\bf x}\vert\vert _p+\vert\vert{\bf y}\vert\vert _p$$
  
  

• if ${\bf x}=f(t)$ is a function, its p-norm is defined as
  
  $$\vert\vert{\bf x}\vert\vert=\left( \int \bigg\vert f(u)\bigg\vert^p\; dt \right)^{1/p}, \;\;\;\;\;\; 1\le p \le \infty$$
  
  

The commonly used p-norms are for $p=1$, $p=2$, and $p=\infty$:

• The absolute sum of all $N$ elements:
  
  $$\vert\vert{\bf x}\vert\vert _1=\sum_{i=1}^n \vert x_i\vert$$
  
  

• Euclidean norm:
  
  $$\vert\vert{\bf x}\vert\vert _2=\sqrt{{\bf x}^T{\bf x}}=\sqrt{\sum_{i=1}^N \vert x_i\vert^2}$$
  
  

• The maximum absolute value of all $N$ elements:
  
  $$\vert\vert{\bf x}\vert\vert _\infty=\max\{ \vert x_1\vert,\cdots, \vert x_n\vert \}$$
  
  

$$\vert\vert{\bf x}\vert\vert _\infty\le\vert\vert{\bf x}\vert\vert _1\le n \vert\vert{\bf x}\vert\vert _\infty$$

$$\vert\vert{\bf x}\vert\vert _\infty\le\vert\vert{\bf x}\vert\vert _2\le \sqrt{n} \vert\vert{\bf x}\vert\vert _\infty$$

$$\vert\vert{\bf x}\vert\vert _2\le\vert\vert{\bf x}\vert\vert _1\le \sqrt{n} \vert\vert{\bf x}\vert\vert _2$$

Out of the three vector norms, the Euclidean 2-norm represents the geometric length of a vector in 2 or 3-D space, which is conserved, or invariant, under rotation, a unitary transform ${\bf y}={\bf R}{\bf x}$ by an orthogonal (orthogonal if in real field) matrix satisfying ${\bf R}^*={\bf R}^{-1}$ or ${\bf R}^*{\bf R}={\bf R}^{-1}{\bf R}={\bf I}$:

$$\vert\vert{\bf y}\vert\vert _2^2={\bf y}^*{\bf y}=({\bf R}{\... ...R}) {\bf x}={\bf x}^*{\bf x}=\vert\vert{\bf x}\vert\vert _2^2$$

i.e., $\vert\vert{\bf y}\vert\vert=\vert\vert{\bf x}\vert\vert$, rotation does not change the length of a vector.

Definition The distance between two points ${\bf x}, {\bf y}\in V$ in a vector space is defined as the norm of the difference ${\bf x}-{\bf y}$.

$$d_p({\bf x},{\bf y})=\vert\vert{\bf x}-{\bf y}\vert\vert _p ... ...N \vert x_i-y_i\vert^p\right)^{1/p},\;\;\;\;(1\le p\le \infty)$$

• $p=1$ (city block or Manhattan distance):
  
  $$d_1({\bf x},{\bf y})=\vert\vert{\bf x}-{\bf y}\vert\vert _1=\sum_{i=1}^N \vert x_i-y_i\vert$$
  
  

• $p=2$ (Euclidean distance):
  
  $$d_2({\bf x},{\bf y})=\vert\vert{\bf x}-{\bf y}\vert\vert _2=\sqrt{\sum_{i=1}^N \vert x_i-y_i\vert^2}$$
  
  

• $p=\infty$ (Chebyshev distance):
  
  $$d_\infty({\bf x},{\bf y})=\vert\vert{\bf x}-{\bf y}\vert\vert _\infty=\max_i \vert x_i-y_i\vert$$
  
  

The three unit circles or spheres, are formed by all points ${\bf x}$ of unity norm $\vert\vert{\bf x}\vert\vert _p=1$ with unity distance to the origin (blue, black, and red for $d_\infty$, $d_2$, and $d_1$, respectively).