Norms

1. Vector Norms

Let x=(x1,,xn)tx = (x_1, \cdots, x_n)^t be an n×1n \times 1 vector.

  • pp-norm: xp=(i=1nxip)1p\left\| x \right\|_p = \left(\sum_{i=1}^n \vert x_i \vert^p\right)^{\frac{1}{p}}
  • 11-norm: x1=i=1nxi\left\| x \right\|_1 = \sum_{i=1}^n \vert x_i \vert
  • 22-norm(Euclidean norm): x2=(i=1nxi2)12\left\| x \right\|_2 = \left(\sum_{i=1}^n \vert x_i \vert^2\right)^{\frac{1}{2}}
  • \infty-norm: x=maxxi\left\| x \right\|_{\infty} = \max \vert x_i \vert
x=limp(i=1nxip)1p=limp(xjp)1p where j=arg maxxi=maxxi\begin{aligned} \left\| x \right\|_{\infty} &= \lim_{p \to \infty} \left(\sum_{i=1}^n \vert x_i \vert^p\right)^{\frac{1}{p}} = \lim_{p \to \infty} \left(\vert x_j \vert^p\right)^{\frac{1}{p}} \text{ where } j = \argmax \vert x_i \vert \\ &= \max \vert x_i \vert \end{aligned}
  • The graphs of x1=x2=x=1\left\| x \right\|_1 = \left\| x \right\|_2 = \left\| x \right\|_{\infty} = 1 for xR2x \in \R^2 are as follows.

PNorms

  • For any vector x\overline{x}, xx2x1\left\| x \right\|_{\infty} \le \left\| x \right\|_2 \le \left\| x \right\|_1. The below image shows this comparison when xR2\overline{x} \in \R^2.

NormComparison

  • Meanwhile, x1nx2\left\| x \right\|_1 \le \sqrt{n} \left\| x \right\|_2, x2nx\left\| x \right\|_2 \le \sqrt{n} \left\| x \right\|_{\infty}, and x1nx\left\| x \right\|_1 \le n \left\| x \right\|_{\infty}.
  • If xp>0\left\| x \right\|_p > 0, then x0x \not = 0.
  • γxp=γxp\left\| \gamma x \right\|_p = \vert \gamma \vert \left\| x \right\|_p where γR\gamma \in \mathbb{R}.
  • x+ypxp+yp\left\| x + y \right\|_p \le \left\| x \right\|_p + \left\| y \right\|_p.
  • xpypxyp\vert \left\| x \right\|_p - \left\| y \right\|_p \vert \le \left\| x - y \right\|_p.

2. Matrix Norms

Suppose that AA is an m×nm \times n matrix and aija_{ij} is the (i,j)(i, j) element of AA. A\left\| A \right\| means the maximum stretching of AA to any vector xx. A=maxx0Axx\begin{aligned} \left\| A \right\| = \max_{x \not = 0} \frac{\left\| Ax \right\|}{\left\| x \right\|} \end{aligned}

  • A1=maxi=1maij\left\| A \right\|_1 = \max \sum_{i=1}^m \vert a_{ij} \vert, which means the largest column sum of AA.
  • A2\left\| A \right\|_2 is the largest singular value of AA, which means the square root of the largest eigenvalue of AtAA^tA.
  • When AA is symmetric, AtAv=A(λv)=λ2vA^tAv = A(\lambda v) = \lambda^2 v where xx and λ\lambda are the eigenvector ane eigenvalue of AA. Then
A2=λmax(AtA)=λmax(A)2=λmax(A)\begin{aligned} \left\| A \right\|_2 = \sqrt{\lambda_{\max} (A^t A)} = \sqrt{\lambda_{\max} (A)^2} = \vert \lambda_{\max} (A) \vert \end{aligned}
  • A=maxi=1naij\left\| A \right\|_{\infty} = \max \sum_{i=1}^n \vert a_{ij} \vert, which means the largest row sum of AA.
  • A>0\left\| A \right\| > 0, then AOA \not = O.
  • γA=γA\left\| \gamma A \right\| = \vert \gamma \vert \left\| A \right\| where γR\gamma \in \mathbb{R}.
  • A+BA+B\left\| A + B \right\| \le \left\| A \right\| + \left\| B \right\|.
  • ABAB\left\| AB \right\| \le \left\| A \right\| \left\| B \right\|.
  • AxAx\left\| Ax \right\| \le \left\| A \right\| \left\| x \right\|.

Reference

[1] Michael T. Heath, Scientific Computing: An Introductory Survey. 2nd Edition, McGraw-Hill Higher Education.


© 2022. All rights reserved.