特征值分解和 SVD 方法介绍
基础知识回顾
核
详见离散数学结构笔记
核（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$ ，其对特征向量进行线性映射之后，结果不会改变特征向量的方向。
这里体现出一种奇妙的变换中的不变性。因此，有一种说法是：
线性变换的特征向量，是指在变换下，方向不变，而只是乘以一个缩放因子的非零向量。
对于一个方阵而言，满足这样性质的向量是稀少的。实际上，相似矩阵（同一线性映射由于经历不同基变换得到的线性映射）拥有相同的特征值。
相似矩阵拥有相同的特征值，未必拥有相同的特征向量，因为所经历的基变换不同。 拥有相同的特征值的不同矩阵，未必相似
特征值的定义式通过变换得到：
$$ ( \lambda \mathrm{E} - A) \alpha = 0 $$
- 其中 $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 $ 的特征向量。
特征值和迹、行列式的关系：
线性变换的特征值之和，等于线性变换的迹。
$$ \sum_{i=1}^{n} \lambda_{i}=\operatorname{tr} A=\sum_{i=1}^{n} a_{i i} $$
线性变换的特征值之积，等于线性变换的行列式：
$$ \prod_{i=1}^{n} \lambda_{i}=\operatorname{det} A $$
实际上，行列式表示线性变换前后勒贝格测度的变化比：
$$ |\det A| = \dfrac{\lambda T(A)}{\lambda (A)} $$
特征值分解
特征值分解（谱分解定理）
设可对角化的方阵 $A \in M_{n}(\mathbb{R}) $， （实数域上的 n 阶方阵） $\lambda_{1} \leq \cdots \leq \lambda_{n}$ 是 $A$ 的 $n$ 个特征值， $w_{1}, \cdots, w_{n}$ 是其 对应的 $n$ 个线性无关的特征向量，则存在正交矩阵 $T$ ，使得
$$ T^{-1} A T=T ^\mathrm{T} A T=\wedge=\left(\begin{array}{ccc} \lambda_{1} & & \ & \ddots & \ & & \lambda_{n} \end{array}\right) . $$
此处 $\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$ 可以分解为三个矩阵的乘积
$$A=U \Sigma V ^\mathrm{T}$$
其中
-
$U$ 是 $ m \times m$ 正交矩阵，称为左奇异向量矩阵，列 $u_{i}$ 称为左奇异向量
-
$V $ 是 $n \times n $ 正交矩阵，称为右奇异向量矩阵，列 $ v_{i} $ 称为右奇异向量.
-
$\Sigma $ 是 $m \times n$ (不严格)对角阵，称为奇异值矩阵，其元素 $$ \sigma_{i j}=\left{\begin{array}{l} 0, i \neq j \ \sigma_{i} \geq 0, i=j \end{array}\right. $$
对角元 $ \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 的矩阵去拟合矩阵。因为：
$$ A=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\ldots+\sigma_{r} u_{r} v_{r}^{\mathrm{T}} $$
在后面我们会继续讨论。
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$ 经过奇异值分解后，可以写成 $$ \begin{aligned} A_{m \times n} &=U_{m \times m} \sum V_{n \times n}^{^\mathrm{T}}=\left(u_{1}, \cdots, u_{m}\right)\left(\begin{array}{ccc} \sqrt{\lambda_{1}} & & \ & \sqrt{\lambda_{2}} & \ & & \ddots \end{array}\right)\left(\begin{array}{c} v_{1}^{^\mathrm{T}} \ \vdots \ v_{n}^{^\mathrm{T}} \end{array}\right) \ &=\sqrt{\lambda_{1}} u_{1} v_{1}^{^\mathrm{T}}+\sqrt{\lambda_{2}} u_{2} v_{2}^{^\mathrm{T}}+\cdots . \end{aligned} $$
没有压缩时表示 $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)$ 时，误差为：
$$ \frac{(m+n) \sum_{i=1}^{k} \lambda_{i}}{(m+n) \sum_{i=1}^{\min {m, n}} \lambda_{i}}=\frac{\sum_{i=1}^{k} \lambda_{i}}{\sum_{i=1}^{\min {m, n}} \lambda_{i}} $$
矩阵的广义逆
设 $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$
$$ \left{\begin{array}{l} A X A=A, X A X=X, \ (A X)^{^\mathrm{T}}=A X,(X A)^{^\mathrm{T}}=X A, \end{array}\right. $$
即 $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^{-1} A V=V ^\mathrm{T} A V=\wedge=\left(\begin{array}{ccc} \lambda_{1} & & \ & \ddots & \ & & \lambda_{n} \end{array}\right) . $$
其中 $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$ 因此是_半正定_的。
考虑矩阵左乘的映射
$$ \begin{aligned} A_{m \times n}: \quad \mathbb{R}^{(n)} & \rightarrow \mathbb{R}^{(m)} \ X & \mapsto A X \end{aligned} $$
设秩 $\operatorname{rank}(A)=r$ ，将 $A $ 作用到 $\mathbb{R}^{(n)}$ 的标准正交基 $\left{v_{1}, \cdots, v_{n}\right}$ 上，根据秩－零化度定理
$$ \operatorname{dim}(\operatorname{ker} A) + \operatorname{dim}(\operatorname{Im} A) = \operatorname{dim}(\mathbb{R} ^{(n)}) = n, $$
$\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 $ 时，有
$$ \left\langle A v_{i}, A v_{j}\right\rangle=v_{i} ^\mathrm{T} A ^\mathrm{T} A v_{j}=\lambda_{j} v_{i} ^\mathrm{T} v_{j}=0 . $$
$\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}$ 单位化，并记
$$ u_{i}=\dfrac{A v_{i}}{\left|A v_{i}\right|}=\dfrac{A v_{i}}{\sqrt{\lambda_{i}}}(i=1, \cdots, r) $$
$\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}$ ， 在这组基下，有
$$ A V=A\left(v_{1}, \cdots, v_{n}\right)=\left(\begin{array}{ccccc} \sigma_{1} u_{1} & & & & \ & \ddots & & & \ & & \sigma_{r} u_{r} & & \ & & & 0 & \ & & & & \ddots \ & & & & & 0 \end{array}\right)=U \sum . $$
其中 $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$