基础知识回顾
核
详见 离散数学结构 笔记
核(kernel):如果 $g \in G_1$ 使得同态 $f:G_1 \to G_2$ 映射的结果是单位元,那么 $g$ 是核中元素,所有满足条件的 $ g$ 是 $ f$ 的核,记作 $\operatorname {Ker} f$。
核不但是第一个群的子群,而且是正规的: $\operatorname {Ker} f \triangleleft G_1$。原因在于 $\forall a, b \in \operatorname {Ker} f, f (ab^{-1}) = f (a) f (b)^{-1} = e_2 e_2^{-1} = e_2$,这说明 $\operatorname {Ker} f \in G_1$。$f (ghg^{-1})$ 在核中,所以满足正规子群的定义。
线性映射 $L:V \to W$ 的核:$\ker (L)=\left\{v\in V:L (v)=\mathbf {0}\right\}$,它是所有能让 L 映射到零向量的 v 的集合,因此也称 零空间。
像和原像:简言之 $f (1) = 2$ ,那么 2 是 1 的像,2 是原像。向量空间 $V$ 在泛函 $F$ 下的像是一个子空间,称为泛函 $F$ 的像,记作 $\operatorname {Im} (F) , \operatorname {Im}(F) = F (V)$
正定和半正定
若有对称矩阵 $A \in M_n (\mathbb {R}) $ 对任意 $n$ 为非零列向量 $\mathbf {x}$ ,总是成立 $\mathbf {x} ^\mathrm {T} A \mathbf {x} > 0$,则称矩阵 $A$ 是正定的,记作 $A \succ 0$ 。总是成立 $\mathbf {x} ^\mathrm {T} A \mathbf {x} >= 0$,则称矩阵 $A$ 是半正定的,记作 $A \succeq 0$ 。
$A \in M_n (\mathbb {R}) $ 表示 A 是 $n \times n$ 的实矩阵。
特征值和特征向量
假设 $A$ 是 $n$ 阶方阵,对于数 $\lambda $ 若存在非零列向量 $\alpha \text {s.t.} A \alpha = \lambda \alpha $ ,则 $\lambda $ 是特征值,$\alpha $ 是对应于 $\lambda $ 的特征向量。
$\lambda $ 可以为 0,$\alpha $ 不能为零,否则零向量就永远是个特征向量,that’s boring(3b1b)
我们知道,对向量左乘一个方阵,表示对向量进行线性运算。而上式表明:
对方阵 $A$ ,其对特征向量进行线性映射之后,结果不会改变特征向量的方向。
这里体现出一种奇妙的变换中的不变性。因此,有一种说法是:
线性变换的特征向量,是指在变换下,方向不变,而只是乘以一个缩放因子的非零向量。
对于一个方阵而言,满足这样性质的向量是稀少的。实际上,相似矩阵(同一线性映射由于经历不同基变换得到的线性映射)拥有相同的特征值。
相似矩阵拥有相同的特征值,未必拥有相同的特征向量,因为所经历的基变换不同。 拥有相同的特征值的不同矩阵,未必相似
特征值的定义式通过变换得到:
- 其中 $E$ 是单位阵,也可以记作 $I$ 。
求 $\alpha \text {s.t.} \alpha \neq \vec {0}$ 即求 $(( \lambda \mathrm {E} - A) ) x = 0$ 的非零解,其存在非零解的充要条件是系数行列式 $\det (\lambda E - A) = 0 $ (这样系数矩阵不满秩,才有非零解)
$ \lambda E - A$ 称为特征矩阵。
$\det (\lambda E - A) $ 称为特征行列式
$\det (\lambda E - A) = 0 $ 称为特征方程,特征方程的解称为特征值(或特征根)
性质:
- 特征行列式非零,则 $\forall c \neq 0, \text {s.t.} c \alpha $ 也是 $\lambda $ 的特征向量。 但一个特征向量只能对应一个特征值
- $\alpha _1, \alpha _2$ 是 $\alpha $ 的特征向量,则二者的线性组合也是 $\lambda $ 的特征向量。
特征值和迹、行列式的关系:
线性变换的特征值之和,等于线性变换的迹。
线性变换的特征值之积,等于线性变换的行列式:
实际上,行列式表示线性变换前后勒贝格测度的变化比:
特征值分解
特征值分解(谱分解定理)
设可对角化的方阵 $A \in M_{n}(\mathbb {R}) $, (实数域上的 n 阶方阵) $\lambda_{1} \leq \cdots \leq \lambda_{n}$ 是 $A$ 的 $n$ 个特征值, $w_{1}, \cdots, w_{n}$ 是其 对应的 $n$ 个线性无关的特征向量,则存在正交矩阵 $T$ ,使得
此处 $\wedge$ 表示对角阵
由 $T^{-1} A T = \wedge $ 可知 $A = T \wedge T^{-1} $ ,其中 $T$ 是将 $A$ 的 $n$ 个特征向量单位化后组成 的 $n \times n$ 矩阵.
于是,我们把 $A$ 分解为了三个矩阵的乘积。
问题:对于方阵,得到其特征值,能够把握其不变性。然而如果 A 不是方阵,我们还可以对 $A$ 进行分解吗?
下面引入 SVD,相比于特征分解(spectral decomposition)它可以对任意矩阵进行分解。
SVD 定理
我们的问题:
- 什么是 SVD?
- SVD 能得到什么?
- SVD 有什么意义?
- 如何进行 SVD?
- 如何证明 SVD?
什么是 SVD
SVD (singular value decomposition)是将矩阵 $A$ 因式分解为三个矩阵乘积 $A = U \Sigma V ^\mathrm {T}$ 的方法。其中 $U,V$ 的列向量正交规范。并且矩阵 D 是各项为正的对角矩阵。
正交规范:通俗而言就是两向量垂直且各自长度为 1
设 $A \in M_{m \times n}(\mathbb {R})$ ,则 $A$ 可以分解为三个矩阵的乘积
其中
- $U$ 是 $ m \times m$ 正交矩阵,称为左奇异向量矩阵,列 $u_{i}$ 称为左奇异向量
- $V $ 是 $n \times n $ 正交矩阵,称为右奇异向量矩阵,列 $ v_{i} $ 称为右奇异向量.
- $\Sigma $ 是 $m \times n$ (不严格) 对角阵,称为奇异值矩阵,其元素
对角元 $ \sigma_{i}$ 称为 $ A $ 的奇异值,通常按 $\sigma_{i} \geq \sigma\_{i+1}(i=1,2, \cdots, n-1) $ 排列,
$A A ^\mathrm {T}$ 的特征向量组成 $U$ 矩阵。
$A ^\mathrm {T} A$ 的特征向量组成 $V$ 矩阵。
特征值和奇异值满足关系 $\sigma_i ^2 = \lambda _i$
我们知道,任意函数都可以用一个多项式拟合出来,换言之,只要确定多项式的系数向量就相当于确定了这个函数。
同样的,奇异值分解可以看作用一系列的秩为 1 的矩阵去拟合矩阵。因为:
在后面我们会继续讨论。
SVD 的算法
分为三部:
- 求解 $A A ^\mathrm {T}$ 和 $A ^\mathrm {T} A$
- 求解 $A A ^\mathrm {T}$ 和 $A ^\mathrm {T} A$ 的特征向量
- 利用 $\sigma_i^2 = \lambda _i$ 得到奇异值矩阵。
SVD 的几何意义
可以参考 此文
一个 $m \times n$ 矩阵 $A$ 经过奇异值分解后,可以写成
没有压缩时表示 $A$ 需要 $m \times n$ 个元素,如果将 $A^{^\mathrm {T}} A$ 的特征值按从大 到小排序,即 $\lambda_{1} \geq \lambda_{2} \geq \cdots \geq \lambda_{\min}\{m, n\}$.
留下 $A$ 的前 $k$ 项,$k$ 越大,越接近原来的矩阵。
$A$ 的最小压缩表示为 $\sqrt {\lambda_{1}} u_{1} v_{1}^{^\mathrm {T}}$ ,需要 $m+n+1$ 个元素。当压缩存储量为 $k (m+n+1)$ 时,误差为:
矩阵的广义逆
设 $A$ 为矩阵,满足 $A X A=A$ 的矩阵 $X$ 称为 $A$ 的广义逆,记为 $A^{-}$ (注意若 $A$ 为 $m \times n$ 矩阵,则 $A^{-}$ 为 $n \times m$ 矩阵).
定理:任意矩阵 $A$ 的广义逆 $A^{-}$ 总存在。事实上,若存在可逆矩阵 $P, Q$ , 使得 $A=P\left (\begin {array}{c} E_{r} \\ \end {array}\right) Q$ ,则 $A^{-}$ 只能为 $A^{-}=Q^{-1}\left (\begin {array}{cc} E_{r} & Y_{2} \\ Y_{3} & Y_{4}\end {array}\right) P^{-1}$ , 其中 $Y_{2}, Y_{3}, Y_{4}$ 的元素是任意的.
矩阵 $A$ 的 Moore-Penrose 广义逆(MP 逆) $A^{+}$ 是指满足下列等式的矩阵 $X$
即 $A, X$ 互为广义逆, $A X, X A$ 为对称阵.
定理:任意矩阵 $A$ 的 Moore-Penrose 广义逆 $A^{+}$ 存在且唯一。事实上,若 $A=C R$ ,其中 $C, R$ 为列、行满秩阵,则 $A^{+}=R^{\prime}\left (R R^{\prime}\right)^{-1}\left (C^{\prime} C\right)^{-1} C^{\prime}$.
SVD 的证明
我们知道 $A$ 是 $m \times n$ 矩阵。则 $A ^\mathrm {T} A \in M_n (\mathbb {R} )$,因此可以进行特征值分解。即存在正交方阵 $V$,使得
其中 $V=\left (v_{1}, \cdots, v_{n}\right)$ ,而 $v_{i}$ 是 $A^\mathrm {T} A $ 的对应于特征值 $ \lambda_{i}$ 的特征向量 $\left\{v_{1}, \cdots, v_{n}\right\}$ 构成 $\mathbb {R}^{(n)} $ 的一组标准正交基.
$A ^\mathrm {T} A$ 是半正定矩阵,故特征值 $\lambda _i \geqslant 0$
转置矩阵左乘自己,结果是对称矩阵。 对任何列向量 $v$ ,$ \mathbf {v} ^\mathrm {T} A ^\mathrm {T} A \mathbf {v} =(A \mathbf {v} ) ^\mathrm {T} (A \mathbf {v} )=(A \mathbf {v} )\cdot (A \mathbf {v} )\geq 0$ 因此是半正定的。
考虑矩阵左乘的映射
设秩 $\operatorname {rank}(A)=r$ ,将 $A $ 作用到 $\mathbb {R}^{(n)}$ 的标准正交基 $\left\{v_{1}, \cdots, v_{n}\right\}$ 上,根据 秩-零化度定理
$\operatorname {dim}(\operatorname {ker} A)$ 表示维度之于 A 的零空间,即零化度 > $\operatorname {dim}(\operatorname {Im} A)$ 表示维度之于 A 的像空间,即 $\operatorname {rank}(A)$ 可以结合 此处 理解
由于 $\operatorname {rank} A = r$,因此可知 $A v_{1}, \cdots, A v_{n}$ 只有 $n$ 个向量是线性无关的,即其中有 $r $ 个向量构成 $\mathbb {R}^{(m)}$ 的一组部分基(其正交性尚且未知),不妨设它们为 $\left\{A v_{1}, \cdots, A v_{r}\right\}$
从上面秩零化度公式可知,$\dim \ker A = n - r$,因此剩下的向量 $v_{r+1} \cdots v_{n}$ 在线性映射 $A$ 作用之后就成为零向量: $A v_{r+1}=A v_{r+2}=\cdots=A v_{n}=0$ .
注意到内积 $\left\langle v_{i}, v_{j}\right\rangle=v_{i} ^\mathrm {T} v_{j}=\delta_{i j} $ ,当 $i \neq j $ 时,有
$\mathbf{Ax}=\lambda\bf x$ 因此 $(\mathbf {A ^\mathrm {T} A})\mathbf x=\mathbf A ^\mathrm {T}(\lambda \mathbf x)=(\lambda \mathbf A ^\mathrm {T})\bf x$ 若 $\mathbf {A}$ 对称,则 $(\mathbf {A ^\mathrm {T} A})\mathbf x=\lambda^2\bf x$
当 $ i=j $ 时,有 $\left|A v_{i}\right|^{2}=\left\langle A v_{i}, A v_{i}\right\rangle=\lambda_{i} v_{i} ^\mathrm {T} v_{i}=\lambda_{i}$ . 从而 $\left\{A v_{1}, \cdots, A v_{r}\right\}$ 是两两正交的,将 $A v_{i}$ 单位化,并记
$\lambda _i \geqslant 0$ ,因为 $A ^\mathrm {T} A$ 是半正定的。 但是 $\lambda _i \neq 0$,因为特征值为零的在零空间中,已经被排除。
于是 $A v_{i}=\sigma_{i} u_{i}$ ,其中 $\sigma_{i}=\sqrt {\lambda_{i}} $. 将 $u_{1}, \cdots, u_{r}$ 扩充成 $\mathbb {R}^{(m)}$ 的标准正交基 $\left\{u_{1}, \cdots, u_{r}, u_{r+1}, \cdots, u_{m}\right\}$ , 在这组基下,有
其中 $U=\left (u_{1}, \cdots, u_{m}\right)$, $ \Sigma=\operatorname {diag}\left (\sigma_{1}, \cdots, \sigma_{r}, 0, \cdots, 0\right)$ , 将上述等式 两边右乘 $V^{-1}$ ,得 $A=U \Sigma V^{\prime}$ .
$\square$