基础知识回顾

核

详见 离散数学结构 笔记

核（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 $ 称为特征方程，特征方程的解称为特征值（或特征根）

性质：

  1. 特征行列式非零，则 $\forall c \neq 0, \text {s.t.} c \alpha $ 也是 $\lambda $ 的特征向量。 但一个特征向量只能对应一个特征值
  2. $\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 的算法

分为三部：

  1. 求解 $A A ^\mathrm {T}$ 和 $A ^\mathrm {T} A$
  2. 求解 $A A ^\mathrm {T}$ 和 $A ^\mathrm {T} A$ 的特征向量
  3. 利用 $\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$

参考

奇异值分解 - castelu