Vector Norms

The norm of a vector ${\bf x}$, denoted by $\vert\vert{\bf x}\vert\vert$, can be intuititvely interpretated as its “size”. For example, the norm of a real number $x\in \mathbb{R}$ in the 1-D real space is its absolute value $\vert x\vert$, or its distance to the origin, and 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. Here is the most general definition of a vector norm:

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

The triangle inequality can also be expressed in alternative forms. If we define ${\bf z}=-{\bf y}$, the triangle inequality becomes

  $\displaystyle \vert\vert{\bf x}-{\bf z}\vert\vert\le \vert\vert{\bf x}\vert\vert+\vert\vert{\bf z}\vert\vert
$ (211)
If we further define ${\bf u}={\bf x}-{\bf z}$, i.e., ${\bf z}={\bf x}-{\bf u}$, then the above becomes
  $\displaystyle \vert\vert{\bf u}\vert\vert\le \vert\vert{\bf x}\vert\vert+\vert\...
...rt\le \vert\vert{\bf x}-{\bf u}\vert\vert
=\vert\vert{\bf u}-{\bf x}\vert\vert
$ (212)
Combining the two results above, we get
  $\displaystyle \vert\vert{\bf x}\vert\vert-\vert\vert{\bf y}\vert\vert\le\vert\v...
...}-{\bf y}\vert\vert\le \vert\vert{\bf x}\vert\vert+\vert\vert{\bf y}\vert\vert
$ (213)
The first equality holds if ${\bf x}$ and ${\bf y}$ are in the same direction, the second equality holds if they are in opposite direction. More specially when ${\bf y}={\bf0}$, both equalities hold.

TriangleInequality1.png

The p-norms of an n-D vector ${\bf x}=[x_1,\cdots,x_n]^T$ and a function $f(x)$ are defined as:

  $\displaystyle \vert\vert{\bf x}\vert\vert _p=\left( \sum_{i=1}^n \vert x_i\vert...
...;
\vert\vert f(x)\vert\vert _p=\left( \int \vert f(x)\vert^p\,dx \right)^{1/p}
$ (214)
The p-norm satisfies the three requirements in the definition of vector norm. The first two are trivially obvious, while the third one happens to be Minkowski's inequality (see appendix):
  $\displaystyle \vert\vert{\bf x}+{\bf y}\vert\vert _p\le \vert\vert{\bf x}\vert\vert _p+\vert\vert{\bf y}\vert\vert _p
$ (215)
The p-norms corresponding to $p=1$, $p=2$, and $p=\infty$ are most commonly used:

Out of the three p-norms, the Euclidean 2-norm is the only one that is unitary invariant, i.e., it is conserved or invariant under any unitary transform ${\bf y}={\bf R}{\bf x}$, where ${\bf R}$ is a unitary matrix satisfying ${\bf R}^{-1}={\bf R}^*$:

  $\displaystyle \vert\vert{\bf y}\vert\vert _2^2={\bf y}^*{\bf y}=({\bf R}{\bf x}...
...,({\bf R}^*{\bf R})\,{\bf x}={\bf x}^*{\bf x}=\vert\vert{\bf x}\vert\vert _2^2
$ (219)
i.e., the length of the vector is not changed by any unitary transform (such as rotation, when ${\bf R}$ is a rotation matrix).

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

  $\displaystyle c\,\vert\vert{\bf x}\vert\vert _b\le \vert\vert{\bf x}\vert\vert _a\le C\,\vert\vert{\bf x}\vert\vert _b
$ (220)
Note that this relationship can also be written as
  $\displaystyle \frac{1}{C}\,\vert\vert{\bf x}\vert\vert _a\le \vert\vert{\bf x}\vert\vert _b\le \frac{1}{c}\,\vert\vert{\bf x}\vert\vert _a
$ (221)

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

Proof

Q.E.D.

The three p-norms are equivalent:

    $\displaystyle \vert\vert{\bf x}\vert\vert _\infty\le\vert\vert{\bf x}\vert\vert _1\le n \vert\vert{\bf x}\vert\vert _\infty$  
    $\displaystyle \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$  
    $\displaystyle \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$  

The distance between two vectors ${\bf x}, {\bf y}\in V$ is defined as the norm of their difference $d({\bf x},{\bf y})=\vert\vert{\bf x}-{\bf y}\vert\vert$. In particular, when ${\bf y}={\bf0}$, the distance $\vert\vert{\bf x}-{\bf0}\vert\vert=\vert\vert{\bf x}\vert\vert$ between ${\bf x}$ and the origin ${\bf0}$ of the space is the norm of ${\bf x}$. Specifically, $d({\bf x},{\bf y})$ can be defined based on the p-norm:

  $\displaystyle d_p({\bf x},{\bf y})=\vert\vert{\bf x}-{\bf y}\vert\vert _p
=\left(\sum_{i=1}^n \vert x_i-y_i\vert^p\right)^{1/p},\;\;\;\;(1\le p\le \infty)
$ (232)
Specially, when

pdist.png

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).