基础知识回顾

详见 离散数学结构 笔记

核(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