矩阵分析与应用-1.4-内积与范数

前言

本文学习过程来源是《矩阵分析与应用-张贤达》一书. 可以通过 z-lib 下载.

一、向量的内积与范数

之前提到向量有常数向量、函数向量和随机向量. 不管怎么变, 其对应的内积和范数都要符合一定的公理. 实向量是复向量的特例, 这里以复向量为例, 用 \(R\) 和 \(C\) 分别代表实数域和复数域.

定义: 令 \(V\) 是复向量空间. 函数 \(\left \langle x,y \right \rangle : V \times V \to C\) 称为向量 \(x\) 与 \(y\) 的内积, 若对所有 \(x,y,z \in V\), 以下内积公理满足:

  1. \(\left \langle x,y \right \rangle \ge 0\)

(1a) \(\left \langle x,y \right \rangle = 0\) , 当且仅当 \(x=0\)

  1. \(\left \langle x+y , z \right \rangle = \left \langle x , z \right \rangle + \left \langle y , z \right \rangle\)

  2. \(\left \langle cx , y \right \rangle = c^*\left \langle x , y \right \rangle\) , 对所有复常数 \(c\) 成立.

  3. \(\left \langle x , y \right \rangle = \left \langle y , x \right \rangle ^ *\)

其中 \(*\) 代表复数共轭.

定义: 令 \(V\) 是复向量空间. 函数 \(\left \| x \right \|: V \to R\) 称为向量 \(x\) 的范数, 若对所有 \(x,y \in V\), 以下范数公理满足:

  1. \(\left \| x \right \| \ge 0\)

(1a) \(\left \| x \right \| = 0\) , 当且仅当 \(x=0\)

  1. \(\left \| cx \right \| = |c| \left \| x \right \|\) , 对所有复常数 \(c\) 成立.

  2. \(\left \| x + y \right \| \le \left \| x \right \| + \left \| y \right \|\) , 对所有复常数 \(c\) 成立.

上述公理是平面欧几里得长度的熟知性质. 满足公理 (1), (2), (3), 但不一定满足公理 (1a) 的函数称为向量的半范数.

1. 常数向量的内积与范数

两个 \(m \times 1\) 维常数向量 \(x = [x_1,x_2,\dots,x_m]^{\mathrm{T}}\) 和 \(y = [y_1,y_2,\dots,y_m]^{\mathrm{T}}\) 的内积 (或叫点积) 定义为:

\[ \left \langle x,y \right \rangle = x^{\mathrm{H}}y = \sum_{i=1}^mx_i^*y_i \tag{1} \]

两个向量之间的夹角定义为

\[ cos\theta \overset{def}{=} \frac{\left \langle x,y \right \rangle}{\sqrt{\left \langle x,x \right \rangle } \sqrt{\left \langle y,y \right \rangle}} = \frac{x^{\mathrm{H}}y}{\left \| x \right \|\left \| y \right \|} \tag{2} \]

显然, 当 \(x^{\mathrm{H}}y=0\)时, \(\theta=\pi/2\). 此时, 称常数向量 \(x\) 和 \(y\) 正交. 因此, 两个常数向量正交的数学定义如下.

定义: 两个常数向量若它们的内积等于零, 即 \(x^{\mathrm{H}}y=0\), 则称这两个向量正交, 并记作 \(x \perp y\).

补充说明: 根据定义, 零向量与任何向量都正交.

常用向量范数:

  1. \(l_1\) 范数

\[ \left \| x \right \|_1 \overset{def}{=} \left | \sum_{i=1}^mx_i \right | = |x_1| + |x_2| + \dots + |x_m| \tag{3} \]

这也叫和范数或者 1 范数. 用作两点间的曼哈顿距离公式如下:

\[ \left \| x - y \right \|_1 \overset{def}{=} \left | \sum_{i=1}^{m}x_i-y_i \right | = |x_1-y_1| + |x_2-y_2| + \dots + |x_m-y_m| \tag{4} \]

  1. \(l_2\) 范数

\[ \left \| x \right \|_2 = (|x_1|^2 + |x_2|^2 + \dots + |x_m|^2)^{1/2} \tag{5} \]

这一范数常称 \(\mathrm{Euclidean}\) (欧几里得) 范数, 有时也称 \(\mathrm{Frobenius}\) 范数. 两个向量之间的该范数就是求欧几里得距离, 简而言之就是求两点间的空间距离.

  1. \(l_{\infty}\) 范数

\[ \left \| x \right \|_{\infty} = \mathrm{max}(|x_1|,|x_2|,\dots,|x_n|) \tag{6} \]

也称无穷范数或极大范数.

  1. \(l_p\) 范数

\[ \left \| x \right \|_p = \left ( \sum_{i=1}^{m}|x_i|^p \right )^{1/2} \quad , \quad p \ge 1 \tag{7} \]

\(l_p\) 范数也叫做 \(\mathrm{Holder}\) 范数.

当 \(p=2\) 时, \(l_p\) 范数与 \(\mathrm{Euclidean}\) 范数完全等价. 另外, 无穷范数是 \(l_p\) 范数的极限形式, 即有

\[ \left \| x \right \|_{\infty} = \lim_{p \to \infty} \left ( \sum_{i=1}^{m}|x_i|^p \right )^{1/p} \tag{8} \]

利用极限的知识就可以证明:

不妨令 \(|a_1| \le |a_i|\), 那么 \[ \lim_{p \to \infty} \left ( \frac{|a_i|}{|a_1|} \right) = \left\{ \begin{array}{c} 1 \quad |a_i| = |a_1| \\ 0 \quad |a_i| < |a_1| \end{array} \right. \\ \]

\[ \lim_{p \to \infty} \left ( \sum_{i=1}^{n}|a_i|^p \right)^{1/p} = \lim_{p \to \infty} \left ( |a_1|^p \sum_{i=1}^{n}\left (\frac{|a_i|}{|a_1|} \right )^p \right )^{\frac{1}{p}} = |a_1| \lim_{p \to \infty}m^{\frac{1}{p}} = |a_1| \quad 0 < m \le n \]

常数向量 \(w\) 和 \(v\) 的外积 (又叫叉积) 记作 \(wv^{\mathrm{H}}\) 定义为

\[ wv^{\mathrm{H}} = \begin{bmatrix} w_1v_1^*& w_1v_2^*& \dots& w_1v_m^* \\ w_2v_1^*& w_2v_2^*& \dots& w_2v_m^* \\ \vdots& \vdots& & \vdots \\ w_mv_1^*& w_mv_2^*& \dots& w_mv_m^* \\ \end{bmatrix} \tag{9} \]

2. 函数向量的内积与范数

若 \(x(t)\) 和 \(y(t)\) 分别是变量 \(t\) 的函数变量, 则它们的内积定义为

\[ \left \langle x(t),y(t) \right \rangle \overset{def}{=} \int_{a}^{b}x^{\mathrm{H}}(t)y(t)dt \tag{10} \]

其中, 变量 \(t\) 在 \([a,b]\) 取值, 且 \(a<b\).

两个函数向量的夹角定义为 \[ cos\theta \overset{def}{=} \frac{\left \langle x,y \right \rangle}{\sqrt{\left \langle x,x \right \rangle } \sqrt{\left \langle y,y \right \rangle}} = \frac{\int_{a}^{b}x^{\mathrm{H}}(t)y(t)dt}{\left \| x \right \|\left \| y \right \|} \tag{11} \]

式中, \(\left \| x(t) \right \|\) 是函数向量 \(x(t)\) 的范数, 定义为

\[\left \| x(t) \right \| \overset{def}{=} \left ( \int_{a}^{b}x^{\mathrm{H}}(t)y(t)dt \right )^{1/2} \tag{12}\]

由此可得, 两函数向量内积为零.

\[ \int_{-\infty}^{\infty} x^{\mathrm{H}}(t)y(t)dt = 0 \]

当 \(\theta = \pi/2\) 时, 这两个函数向量正交, 并记作 \(x(t) \perp y(t)\).

3. 随机向量的内积与范数

若 \(x(\xi)\) 和\(y(\xi)\) 分别是样本变量 \(\xi\) 的随机向量, 则它们的内积定义为

\[ \left \langle x(\xi),y(\xi) \right \rangle \overset{def}{=} E \left \{x^{\mathrm{H}}(\xi)y(\xi) \right \} \tag{13} \]

随机向量 \(x(\xi)\) 的范数定义为 \[ \left \| x(\xi) \right \|^2 \overset{def}{=} E \left \{x^{\mathrm{H}}(\xi)y(\xi) \right \} \tag{14} \]

与常数向量和函数向量不同的是, 若\(m \times 1\) 随机向量 \(x(\xi)\) 的任意元素与 \(n \times 1\) 随机向量 \(y(\xi)\) 的任意元素正交. 则 \(x(\xi)\) 和 \(y(\xi)\) 称为正交. 这意味着两个向量的互相关矩阵为零矩阵 \(O_{m \times n}\), 即

\[ E \left \{x(\xi)y^{\mathrm{H}}(\xi) \right \} = O_{m \times n} \tag{15} \]

并记作 \(x(\xi) \perp y(\xi)\).

二、向量的相似度

考虑 \(M\) 个类型的模式, 它们分别记作 \(\omega_1,\omega_2,\dots,\omega_M\). 假设通过已知类型属性的观测样本, 比如已抽取出 \(M\) 个样本模式向量 \(s_1,s_2,\dots,s_M\). 给定一任意的位置模式向量 \(x\), 判断属于哪一类模式, 这个问题称为模式分类.

这不就是机器学习中的分类问题吗? 模式分类的基本思想就是将未知模式向量 \(x\) 同 \(M\) 个样本模式向量进行对比, 看 \(x\) 与哪一个样本模式向量最相似, 并据此做出模式分类的判断.

用\((x,s_1), (x,s_2), \dots, (x,s_M)\) 分别作为未知模式向量\(x\) 和已知样本模式向量 \(s_1,s_2,\dots,s_M\) 之间的相似关系的符号. 以 \(x\) 与 \(s_1,s_2\) 的相似关系为例, 若

\[ (x,s_1) \le (x,s_2) \tag{16} \]

则称未知模式向量 \(x\) 与样本模式向量 \(s_2\) 更相似. 建立这样的关系需要定义相似度和相异度.

最简单的就是两个向量之间的欧几里得距离. 未知模式向量 \(x\) 与 第 \(i\) 个样本模式向量 \(s_i\) 之间的欧几里得距离记作 \(D(s_i,x)\), 定义为 \[ D(s_i,x) = \left \langle x-s_i \right \rangle_2 = \sqrt{(x-s_i)^{\mathrm{T}}(x-s_i)} \tag{17} \]

称 \(s_i \in \left \{ s_1,s_2,\dots,s_M \right \}\) 是到 \(x\) 的近邻 (即最近的邻居), 若

\[ D(s_i,x) = \underset{k}{min}D(s_k,x), \quad k = 1,2,\dots,M \tag{18} \]

这就是机器学习中大名鼎鼎的 KNN 算法的来源.

然后换做马氏距离来算, 令

\[ m = \frac{1}{N}\sum_{k=1}^{N}s_i \tag{19} \]

代表 \(N\) 个样本模式向量的均值向量, 并使用

\[ C = \frac{1}{N}\sum_{i=1}^{N}(s_i-m)(s_i-m)^{\mathrm{T}} \tag{20} \]

代表 \(N\) 个样本模式向量的协方差矩阵.

从未知模式向量 \(x\) 到均值向量 \(m\) 之间的 \(\mathrm{Mahalanobis}\) 距离定义为

\[ D(m,x)=(x-m)^{\mathrm{T}}C(x-m)\tag{21} \]

类似地, 从第 \(i\) 个样本模式向量 \(s_i\) 到均值向量 \(m\) 的 \(\mathrm{Mahalanobis}\) 定义为

\[ D(m,s_i)=(s_i-m)^{\mathrm{T}}C(s_i-m)\tag{22} \]

根据近邻分类法, 将未知模式向量 \(x\) 归为满足

\[ D(s_i,x)= \underset{k}{min}|D(s_k,x) - D(m,x)|,\quad k = 1,2,\dots,N \tag{23} \]

的近邻 \(s_i\) 的模式类型.

当然两个向量之间的相似度还可以用夹角的余弦函数 \[ S(s_i,x) = cos(\theta_i)=\frac{x^{\mathrm{T}}s_i}{\left \| x \right \|_2 \left \| s_i \right \|_2} \tag{24} \]

当 \(cos(\theta_i) < cos(\theta_j), \forall j \neq i\) 成立, 则认为未知模式向量 \(x\) 与样本模式向量 \(s_i\) 最相似.

式子 (24) 还可变形成为 \[ S(s_i,x)=\frac{x^{\mathrm{T}}s_i}{x^{\mathrm{T}}x + s^{\mathrm{T}}_is_i + x^{\mathrm{T}}s_i} \tag{25} \]

称为 \(\mathrm{Tanimoto}\) 测度, 广泛应用于信息恢复、疾病分类、动植物分类.

待分类的信号称为目标信号, 分类通常是根据某种物理或几何概念进行的. 令 \(X\) 为目标信号, \(A_i\)代表第\(i\)类目标的分类概念. \[ (X,A_i) \le (X,A_j), \forall i,j \tag{26} \]

这类有效关系一般用于目标-概念距离 \(D(X,A_i)\) 描述. 因此, 若目标-概念距离 \(D(X,A_i)\) 最小, 则将 \(X\) 归为第 \(i\) 类目标 \(C_i\).

三、正交向量在移动通信中的应用

1. 时分多址

在计算机网络中学过这样的概念, 就是单通道在把一段时间划给多个用户. 这个操作就更像操作系统中采用时间片轮转的调度形式.

2. 频分多址

不同用户占据不同频段. 日常生活中显而易见的就是收音机的不同频段可以同时收听到. 这就像计算机体系架构中多核CPU的运行, 它们是并行的概念.

3. 跳频-码分多址

先划分时间, 再划分频段. 就像是时分和频分的结合.

4. 直接序列-码分多址

同时通信, 共享频道. 因为每个用户的扩频码向量之间是互相正交, 互不影响.

四、向量范数用作 Lyapunov 函数

\(\mathrm{Lyapunov}\) 直接法是分析和构造线性和非线性控制系统最成功的工具之一.

定理 1: (\(\mathrm{Lyapunov}\) 稳定性定理) 若对连续系统 \(dot{x}=f(x)\) 或 离散系统 \(x_{k+1} = f(x_k)\) 存在一个函数 \(V(x)\) 具体平衡点 \(x=0\), 且 \(V\) 在整个 \(R^n\) 内满足条件:

  1. \(V\) 是正定和径向无界函数.

  2. 对 \(x \neq 0\)

\[ DV = \lim_{\Delta t \to 0}sup{\frac{V(x(t+\Delta t))-V(x(t))}{\Delta t}} < 0 \quad (连续系统) \]

或

\[ \Delta V = V(x_{k+1}) - V(x_k) < 0 \quad (离散系统) \]

则平衡点 \(x=0\) 是全局渐近稳定的.

在向量 \(x\) 的 \(n\) 维空间内, 考虑用向量范数

\[ V(x) = \left \| Wx \right \| \]

其中 \(W=[\omega_1,\omega_2,\dots,\omega_n]\) 是 \(m \times n\) 矩阵, 且 \(m \ge n\) 和 \(\mathrm{rank}(W)=n\)

\(l_p\) 范数构成了一类特殊的向量范数, 其中 \(\mathrm{Euclidean}\) 范数 \[ V(x) = \left \| Wx \right \|_2 = \left ( \sum_i|\omega_i^{\mathrm{T}}x|^2\right )^{1/2} \tag{27} \]

和无穷范数 \[ V(x) = \left \| Wx \right \|_{\infty} = \lim_{p \to \infty}\left ( \sum_i|\omega_i^{\mathrm{T}}x|^p\right )^{1/p} = \underset{i}{\mathrm{max}}\{ \omega_i^{\mathrm{T}}x\} \tag{28} \]

是 \(\mathrm{Lyapunov}\) 函数的两个重要例子.

定理 2: 函数 \(V(x) = \left \| Wx \right \|\) (其中, \(W\) 是 \(m \times n\) 矩阵, 且 \(\mathrm{rank}W = n\)) 是系统 \(\dot{x} = Ax\) 的 \(\mathrm{Lyapunov}\) 函数, 当且仅当矩阵 \(W\) 是矩阵方程 \[ WA - QW = O \tag{29} \]

的解, 假定矩阵 \(Q\) 满足条件 \[ \mu(Q) < 0 \tag{30} \]

其中 \[ \mu(Q) = \lim_{\Delta t \to 0+} \frac{\left \| I + \Delta tQ - 1 \right \|}{\Delta t} \tag{31} \]

\(\mu(Q)\) 有时称为矩阵 \(Q\) 的对数矩阵范数. 对数矩阵范数可以是复数, 这一点和矩阵范数非负性质相违背.

如果式子 (28) 的函数是 \(\mathrm{Lyapunov}\) 函数, 那么它的平方 \[ V^2(x) = \left \| Wx \right \|_2^2 = \sum_{i=1}^n(\omega_i^{\mathrm{T}}x)^2 = x^{\mathrm{T}}W^{\mathrm{T}}Wx \tag{32} \]

也是 \(\mathrm{Lyapunov}\) 函数. 式子 (32) 的函数为二次型 \(x^{\mathrm{T}}Rx\), 其中 \[ R = W^{\mathrm{T}}W \tag{33} \]

这样的二次型函数是系统 \(\dot{x}=Ax\) 的\(\mathrm{Lyapunov}\) 函数, 当且仅当 \[ A^{\mathrm{T}}R + RA = -\tilde{Q} \tag{34} \]

的解 \(\tilde{Q}\) 是一个正定对称矩阵.

定理 3: 下面两个集合等价: \[ L_1 = \{ R \in R^{n \times n}|A^{\mathrm{T}}R+RA = -\tilde{Q}, 其中, \tilde{Q},R > 0, \tilde{Q} 对称 \} \tag{35} \]

\[ L_2 = \{ R \in R^{n \times n}|R=W^{\mathrm{T}}W, WA - QW = O , 其中, \mu_2(Q) < 0, \mathrm{rank}(W)=n \} \tag{36} \]

感觉这部分和机器学习没有太大关系, 如果以后遇到了或者其他什么原因再来学习吧.

五、矩阵的范数和内积

作为一种算子, 实矩阵 \(A \in R^{m \times n}\) 的范数记作 \(\left \| A \right \|\), 它是矩阵的实值函数, 必须要满足一些条件:

  1. 对于任何非零矩阵 \(A \neq O\), 其范数大于零, 即 \(\left \| A \right \| > 0\), 并且 \(\left \| O \right \| = 0\)

  2. 对于任意复数 \(c\) 有 \(\left \| cA \right \| = |c|\left \| A \right \|\)

  3. 矩阵范数满足三角不等式 \(\left \| A+B \right \| \le \left \| A \right \| + \left \| B \right \|\)

  4. 两个矩阵乘积的范数小于或等于两个矩阵范数的乘积, 即 \(\left \| AB \right \| \le \left \| A \right \| \left \| B \right \|\)

有几个典型的矩阵范数

  1. \(\mathrm{Frobenius}\) 范数 \[ \left \| A \right \|_F \overset{def}{=} \left ( \sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij}|^2 \right )^{1/2} \tag{37} \]

这个范数也叫做矩阵的 \(l_2\) 范数

  1. \(l_p\) 范数 \[ \left \| A \right \|_p \overset{def}{=} \underset{x \neq 0}{\mathrm{max}} \frac{\left \| Ax \right \|_p}{\left \| x \right \|_p} \tag{38} \]

式子中, \(\left \| x \right \|_p\) 是向量 \(x\) 的 \(l_p\) 范数. 这个矩阵范数也称 \(\mathrm{Minkowski} p\) 范数, 或者直接叫做 \(p\) 范数.

  1. 行和范数 \[ \left \| A \right \|_{row} = \underset{1 \le i \le m}{\mathrm{max}} \left \{ \sum_{j=1}^{n} |a_{ij}|\right \} \tag{39} \]

  2. 列和范数 \[ \left \| A \right \|_{col} = \underset{1 \le j \le n}{\mathrm{max}} \left \{ \sum_{i=1}^{m} |a_{ij}|\right \} \tag{40} \]

  3. 谱范数 \[ \left \| A \right \|_{spec} = \sigma_{max} = \sqrt{\lambda_{\mathrm{max}}} \tag{41} \]

式子中, \(\sigma_{max}\) 是矩阵 \(A\) 的最大奇异值, 即 \(A^{\mathrm{H}}A\) 的最大特征值 \(\lambda_{\mathrm{max}}\) 的正平方根. 谱范数也称最大奇异值范数或者算子范数.

  1. \(\mathrm{Mahalanobis}\) 范数 \[ \left \| A \right \|_{\Omega} = \sqrt{tr(A^{\mathrm{H}} \Omega A)} \tag{42} \]

式子中, \(\Omega\) 为正定矩阵 (所有特征值大于零的矩阵), \(tr(A^{\mathrm{H}} \Omega A)\) 为矩阵 \(A^{\mathrm{H}} \Omega A\) 的迹 (对角线之积).

若 \(A,B\) 是 \(m \times n\) 矩阵, 则矩阵的范数具有以下性质: \[ \left \| A+B \right \| + \left \| A-B \right \| = 2(\left \| A \right \|^2 + \left \| B \right \|^2) \tag{43} \]

\[ \left \| A+B \right \| \left \| A-B \right \| \le \left \| A \right \|^2 + \left \| B \right \|^2 \tag{44} \]

与矩阵范数有联系的量是矩阵的内积, 对于任意 \(m \times n\) 复矩阵 \(A\) 和 \(B\), 矩阵的内积记作 $A,B \(, 定义为\)$ A,B = A^{}B $$

以下是矩阵的内积与范数之间的关系

  1. \(\mathrm{Cauchy-Schwartz}\) 不等式 \[ |\left \langle A,B \right \rangle |^2 \le \left \| A \right \|^2 \left \| B \right \|^2 \tag{46} \]

当且仅当 \(A=cB\), 等号成立, 其中, \(c\) 是某个复常数.

  1. \(\mathrm{Pathagoras}\) 定理 \[ \left \langle A,B \right \rangle^2 = 0 \Rightarrow \left \| A+B \right \|^2 = \left \| A \right \|^2 + \left \| B \right \|^2 \tag{47} \]

  2. 极化恒等式 \[ Re(\left \langle A,B \right \rangle) = \frac{1}{4}(\left \| A+B \right \|^2 - \left \| A-B \right \|^2) \tag{48} \]

\[ Re(\left \langle A,B \right \rangle) = \frac{1}{2}(\left \| A+B \right \|^2 - \left \| A \right \|^2 - \left \| B \right \|^2) \tag{49} \]

式子中, \(Re(.)\) 表示取复数的实部.