矩阵和向量的范式(Norms for Vectors and Matrices)

1 内积和范式的定义(Definitions of norms and inner product)

向量范式的定义(vector norm)

定义 1.1. 令 $V$V 是定义在场 $\mathbf{F}$F($\mathbf{F} = \mathbf{R}$F=R 或者 $\mathbf{C}$C，即实数域或者是复数域)上的向量空间。 如果对于任意的$x, y \in V$x,y∈V 和 $c\in \mathbf{F}$c∈F都满足下面几个条件，则称函数 $\|\cdot\|:V\to \mathbf{R}$∥⋅∥:V→R 是一个范式 (有时被称为向量范式vector norm)。
$\begin{aligned} &\text{(1)} \quad \|x\| \ge 0\ \qquad &\text{Nonnegativity（非负）}\\ &\text{(1a)} \quad \|x\| = 0 \text{ if and only if }x=0 \qquad &\text{Positivity（永正）}\\ &\text{(2)} \quad \| cx \| = |c| \|x\| \qquad &\text{Homogeneity（同质）} \\ &\text{(3)} \quad \| x+y \| \le \|x\| + \|y\| \qquad &\text{Triangle Inequality（三角不等）} \\ \end{aligned}$​(1)∥x∥≥0 (1a)∥x∥=0 if and only if x=0(2)∥cx∥=∣c∣∥x∥(3)∥x+y∥≤∥x∥+∥y∥​Nonnegativity（非负）Positivity（永正）Homogeneity（同质）Triangle Inequality（三角不等）​

Positivity(1a)和Homogeneity(2)保证了对于任意非零向量$x$x，可以正则化到单位向量 $u=\frac{x}{\|x\|}$u=∥x∥x​。

只满足(1),(2),(3)而不满足(1a)的范式称为半范式(seminorm)，(1a)保证了只有零向量的范式才是0，非零向量的范式都大于0，而一个非零向量的半范式可以是0。

引理 1.2. $\|\cdot\|$∥⋅∥是定义在实数域或者复数域向量空间 $V$V 上的半范式, 则对于任意 $x, y\in V$x,y∈V，有 $ | |x| − |y|| \le |x − y|$

Proof. 也就是证明$\pm (\|x\| − \|y\|) \le \|x − y\|$±(∥x∥−∥y∥)≤∥x−y∥
$\|x\| =\|x-y+y\| \le \|x-y\|+\|y\| \\ \Rightarrow \|x-y\| \ge \|x\| - \|y\| \\ \|y\| =\|y-x+x\| \le \|y-x\|+\|x\| = \|x-y\|+\|x\|\\ \Rightarrow \|x-y\| \ge \|y\| - \|x\| \\$∥x∥=∥x−y+y∥≤∥x−y∥+∥y∥⇒∥x−y∥≥∥x∥−∥y∥∥y∥=∥y−x+x∥≤∥y−x∥+∥x∥=∥x−y∥+∥x∥⇒∥x−y∥≥∥y∥−∥x∥

内积定义(inner product)

定义 1.3. 令 $V$V 是定义在场 $\mathbf{F}$F($\mathbf{F} = \mathbf{R}$F=R or $\mathbf{C}$C)上的向量空间。 如果对于任意 $x, y, z \in V$x,y,z∈V 和 $c\in \mathbf{F}$c∈F，函数 $\left< \cdot ,\cdot \right>:V\times V\to \mathbf{F}$⟨⋅,⋅⟩:V×V→F 满足下列条件，则它是一个内积(inner product)
$$
\begin{aligned}
&\text{(1)} \left< x,x \right> \ge 0\ \qquad &\text{Nonnegativity（非负）}\
&\text{(1a)} \left< x,x \right> = 0 \text{ if and only if }x=0 \qquad &\text{Positivity（永正）}\
&\text{(2)} \left< x+y,z \right> = \left< x,z \right>+\left< y,z \right> \qquad &\text{Additivity（加法）} \
&\text{(3)} \left< cx,y \right> = c\left< x,y \right> \qquad &\text{Homogeneity（同质）} \
&\text{(4)} \left< x,y \right> = \overline{\left< y,x \right>} \qquad &\text{Hermitian Property（共轭对称性）} \

\end{aligned}
$$
只满足(1), (2), (3), (4)而不满足(1a)的称为semi-inner product。

柯西施瓦茨不等式

定理 1.4(Cauchy-Shwarz inequality). $\left< \cdot ,\cdot \right>$⟨⋅,⋅⟩是定义在向量空间$V$V 上的内积，则对于任意$x,y\in V$x,y∈V
${\left |\left< x ,y \right> \right|}^2 \le \left< x ,x \right>\left< y ,y \right> \quad$∣⟨x,y⟩∣2≤⟨x,x⟩⟨y,y⟩
当且仅当(if and only if) x 和 y 线性相关(linearly dependent)，不等式取等号。

标量形式表示为$(\sum_{i=1}^{n}x_iy_i)^2 \le (\sum_{i=1}^{n}x_i^2 )(\sum_{i=1}^{n}y_i^2)$(∑i=1n​xi​yi​)2≤(∑i=1n​xi2​)(∑i=1n​yi2​)

Proof. 令$x,y\in V$x,y∈V，若$x=y=0$x=y=0，则不等式显然成立，所以假设其中一个是非零向量，不失一般性，假设$y\ne 0$y​=0，令$v=\left< y ,y \right>x - \left< x ,y \right>y$v=⟨y,y⟩x−⟨x,y⟩y，有：
$0\le \left< v,v \right>=\left< \left< y ,y \right>x - \left< x ,y \right>y ,\left< y ,y \right>x - \left< x ,y \right>y \right> \\ =\left< y ,y \right>^2 \left< x,x \right> -\left< y,y \right>\overline{ \left< x,y \right>}\left< x,y \right>-\left< x,y \right>\left< y,x \right> \left< y,y \right> + \left< y,y \right>\overline{ \left< x,y \right>}\left< x,y \right> \\ =\left< y ,y \right>^2\left< x,x \right> - \left< y ,y \right> {\left |\left< x,y \right> \right|}^2 \\ =\left< y ,y \right>(\left< x,x \right>\left< y ,y \right>-{\left |\left< x,y \right> \right|}^2)$0≤⟨v,v⟩=⟨⟨y,y⟩x−⟨x,y⟩y,⟨y,y⟩x−⟨x,y⟩y⟩=⟨y,y⟩2⟨x,x⟩−⟨y,y⟩⟨x,y⟩​⟨x,y⟩−⟨x,y⟩⟨y,x⟩⟨y,y⟩+⟨y,y⟩⟨x,y⟩​⟨x,y⟩=⟨y,y⟩2⟨x,x⟩−⟨y,y⟩∣⟨x,y⟩∣2=⟨y,y⟩(⟨x,x⟩⟨y,y⟩−∣⟨x,y⟩∣2)
因为$y\ne 0$y​=0，即$\left< y ,y \right> > 0$⟨y,y⟩>0，则推出$\left< x,x \right>\left< y ,y \right>-{\left |\left< x,y \right> \right|}^2 \ge 0$⟨x,x⟩⟨y,y⟩−∣⟨x,y⟩∣2≥0，只有当$v=0$v=0的时候，等式成立，即$v=\left< y ,y \right>x - \left< x ,y \right>y=0$v=⟨y,y⟩x−⟨x,y⟩y=0，也就是说$x$x和$y$y线性依赖。

推论 1.5. 如果 $\left< \cdot ,\cdot \right>$⟨⋅,⋅⟩ 是定义在实数或者复数域向量空间 $V$V 上的内积，则函数 $\|\cdot\|:V\to [0,\infty)$∥⋅∥:V→[0,∞)， $\|x\|= \left< x,x \right>^{1/2}$∥x∥=⟨x,x⟩1/2 是向量空间 $V$V 上的一个范式。这样的范式(norm)被称为从内积获得(derived from an inner product)。

---

2 向量的范式

$l_1\text{-morm}$l1​-morm

$\mathbf{C}^n$Cn上的和范式(sum norm)，也叫l1-范式(l1-norm)，定义如下:
$\|x\|_1=|x_1|+\cdots+|x_n|$∥x∥1​=∣x1​∣+⋯+∣xn​∣
通常也被称为曼哈顿范式(Manhattan norm)。

$l_2\text{-morm}$l2​-morm

一个向量$x=[x_1,...,x_n]^T\in \mathbf{C}^n$x=[x1​,...,xn​]T∈Cn的欧几里得范式(Euclidean norm)，也叫l2范式(l2-norm)，定义如下：
$\|x\|_2=(|x_1|^2+\cdots+|x_n|^2)^{1/2}$∥x∥2​=(∣x1​∣2+⋯+∣xn​∣2)1/2
经常使用$\|x-y\|_2$∥x−y∥2​来衡量两个点$x,y\in \mathbf{C}^n$x,y∈Cn的欧几里得距离(Euclidean distance)。

$l_\infty\text{-morm}$l∞​-morm

$\mathbf{C}^n$Cn上的max norm($l_\infty$l∞​-norm)为：
$\|x\|_\infty= \max \{|x_1|,\cdots,|x_n| \}$∥x∥∞​=max{∣x1​∣,⋯,∣xn​∣}
一般的，$\mathbf{C}^n$Cn上的$l_p$lp​-norm定义为：
$\|x\|_p=(|x_1|^p+\cdots+|x_n|^p)^{1/p},\quad p\ge 1$∥x∥p​=(∣x1​∣p+⋯+∣xn​∣p)1/p,p≥1

以二维向量$\mathbf{v}=(v_1, v_2)$v=(v1​,v2​)举例，范式的值恰好为1的图像如下，其中横轴代表$v_1$v1​，纵轴代表$v_2$v2​

l1范式，即$\|v\|_1=|v_1|+|v_2|=1$∥v∥1​=∣v1​∣+∣v2​∣=1

l2范式，即$\|v\|_2=\sqrt{|v_1|^2+|v_2|^2}=1$∥v∥2​=∣v1​∣2+∣v2​∣2​=1

Infinity范式，即$\|v\|_\infty= \max \{|v_1|,|v_2| \}=1$∥v∥∞​=max{∣v1​∣,∣v2​∣}=1

$\mathbf{C}^n$Cn上的k-norms，融合max norm和sum norm，即选k个最大的：
$\|x\|_{[k]}= |x_{i_1}|,\cdots,|x_{i_k}| ,\text{in which }|x_{i_1}|\ge \cdots \ge |x_{i_k}|$∥x∥[k]​=∣xi1​​∣,⋯,∣xik​​∣,in which ∣xi1​​∣≥⋯≥∣xik​​∣

Let $S\in M_{m,n}$S∈Mm,n​ have full column rank, so $m\ge n$m≥n .Let $\|\cdot\|$∥⋅∥ be a given norm on $C^m$Cm and define
$\|x\|_S=\|Sx\|$∥x∥S​=∥Sx∥
for $x\in C^n$x∈Cn.Then $\|\cdot \|_S$∥⋅∥S​ is a norm on $C^n$Cn.

Consider the complex vector space $V = M_{m,n}$V=Mm,n​ with the Frobenius inner product:
$⟨A,B⟩_F =tr B^* A$⟨A,B⟩F​=trB∗A

The norm derived from the Frobenius inner product is the l2-norm(Frobenius norm) on $M_{m,n}:\|A\|_2 = (tr A^* A)^{1/2}$Mm,n​:∥A∥2​=(trA∗A)1/2

---

6 Matrix norms

矩阵范式(matrix norm)定义如下：

A function $| \| \cdot \| |$∣∥⋅∥∣ : $M_n \to R$Mn​→R is a matrix norm if, for all $A, B \in M_n$A,B∈Mn​, it satisfies the following five axioms:
$\begin{aligned} &(1)\quad | \| A \| | \ge 0 \\ &(1a)\quad | \| A \| | = 0 \text{ if and only if } A = 0 \\ &(2) \quad| \| cA \| | = |c| | \| A \| | \text{ for all } c \in C \\ &(3)\quad | \| A+B \| | \le | \| A \| | + | \| B \| | \\ &(4)\quad | \| AB \| | \le | \| A \| | | \| B \| | \\ \end{aligned}$​(1)∣∥A∥∣≥0(1a)∣∥A∥∣=0 if and only if A=0(2)∣∥cA∥∣=∣c∣∣∥A∥∣ for all c∈C(3)∣∥A+B∥∣≤∣∥A∥∣+∣∥B∥∣(4)∣∥AB∥∣≤∣∥A∥∣∣∥B∥∣​

matrix norm有时被称为ring norm， 可以看出前四个属性的定义和norm的一样，矩阵范式多了(4)。如果只满足前四个而不满足(4)，则称之为vector norm on matrices, 有时也称为generalized matrix norm。

由性质(4)，$\quad | \| A^2 \| | \le | \| A \| | | \| A \| | \le | \| A \| |^2$∣∥A2∥∣≤∣∥A∥∣∣∥A∥∣≤∣∥A∥∣2，若$A^2 = A$A2=A，则有$| \| A \| |\ge 1$∣∥A∥∣≥1。所以可推出$| \| I \| | \ge 1$∣∥I∥∣≥1，若A是非奇异矩阵(non-singular)，有$I=A^{-1}A$I=A−1A，$\quad | | I| | \le | | A^{-1} | | \cdot | | A | | $，可以获得一个下界，$，可以获得一个下界，| | A^{-1} | | \ge \frac{| | I| |}{| | A | |}$ ,

$l_1$l1​-norm

对于矩阵$A\in M_n$A∈Mn​，它的$l_1$l1​-norm定义为，
$\| A \|_1= \sum_{i,j=1}^{n} |a_{ij}|$∥A∥1​=i,j=1∑n​∣aij​∣

$l_2$l2​-norm (Frobenius norm, Schur norm, or Hilbert–Schmidt norm)

$\| A \|_2= | tr AA^{*} |^{1/2} =\left ( \sum_{i,j=1}^{n} |a_{ij}|^2 \right )^{1/2}$∥A∥2​=∣trAA∗∣1/2=(i,j=1∑n​∣aij​∣2)1/2

---

7 Vector norms on matrices

---