线性代数（14）：奇异值分解（Singular Value Decomposition）

清华大学线性代数（2）课程第三讲：奇异值分解

参考资料:
清华大学数学科学系-线性代数-马辉
《工程数学 线性代数 第六版》 同济大学数学系 高等教育出版社
Linear Algebra by Gilbert Strang MIT麻省理工线性代数公开视频课，非常推荐！

问题：如何“对角化”$m \times n$矩阵？

1.奇异值分解（Singular Value Decomposition）

设$A$是一个$m \times n$矩阵，则存在$m$阶正交矩阵$U$和$n$阶正交矩阵$V$，满足

$$A=U\left(\begin{array}{cccc} {\sigma_{1}} & {} & {} & {} \\ {} & {\ddots} & {} & {} \\ {} & {} & {\sigma_{r}} & {} \\ {} & {} & {} & {0} \end{array}\right) V^{T}=: U \Sigma V^{T}$$

其中$r=\operatorname{rank} A$。习惯上，设$\sigma{1} \geq \sigma{2} \geq \cdots \geq \sigma{r}>0$。称$\sigma{1}, \cdots, \sigma_{r}$为奇异值（singular value）。称$U$和$V$的前r列向量为奇异向量（singular vector）。这个分解为奇异值分解，简称$SVD$，它是线性代数中最重要的一类分解。

其中矩阵$U$和矩阵$V$用列向量表示为：

$$U=\left(\mathbf{u}_{1} \cdots \mathbf{u}_{r} \mathbf{u}_{r+1} \cdots \mathbf{u}_{m}\right), V=\left(\mathbf{v}_{1} \cdots \mathbf{v}_{r} \mathbf{v}_{r+1} \cdots \mathbf{v}_{n}\right)$$

因为$U$和$V$都是正交矩阵，所以有

$$A_{m \times n} V_{n \times n}=U_{m \times m} \Sigma_{m \times n}$$

其中$V^{T} V=I{n}, U^{T} U=I{m}$，也可以把奇异值分解描述为$r$个秩一矩阵之和

$$\begin{aligned} &A=U \Sigma V^{T},(SVD)\\ &A=\sigma_{1} \mathbf{u}_{1} \mathbf{v}_{1}^{T}+\cdots+\sigma_{r} \mathbf{u}_{r} \mathbf{v}_{r}^{T} \end{aligned}$$

还有

$$\begin{aligned} A \mathbf{v}_{i} &=\sigma_{i} \mathbf{u}_{i}\quad(i=1, \cdots, r) \\ A^{T} \mathbf{u}_{i} &=\sigma_{i} \mathbf{v}_{i}\quad(i=1, \cdots, r) \\ A \mathbf{v}_{j}=& \mathbf{0}\quad(j=r+1, \cdots, n) \\ A^{T} \mathbf{u}_{k} &=\mathbf{0}\quad(k=r+1, \cdots, m) \end{aligned}$$

有

$$\Rightarrow A^{T} A \mathbf{v}_{i}=\sigma_{i}^{2} \mathbf{v}_{i}, \quad A A^{T} \mathbf{u}_{i}=\sigma_{i}^{2} \mathbf{u}_{i} \quad(1 \leq i \leq r)$$

$\mathbf{v}{i}$是矩阵$A^{T} A$对应与特征值$\sigma{i}^{2}$的特征向量，$\mathbf{u}{i}$是矩阵$A A^{T}$对应与特征值$\sigma{i}^{2}$的特征向量。

矩阵$A A^{T}$与$A^{T} A$的特征值和特征向量的性质

设$A$是秩为$r$的$m \times n$实矩阵，则$A A^{T}$为$m$阶实对称矩阵，$A^{T} A$为$n$阶实对称矩阵
（1）$A A^{T}$与$A^{T} A$的特征值为非负数
证明：设$A^{T} A \mathbf{x}=\lambda \mathbf{x}(\mathbf{x} \neq \mathbf{0})$，则$\mathbf{x}^{T} A^{T} A \mathbf{x}=\lambda \mathbf{x}^{T} \mathbf{x}$，即

$$\|A \mathbf{x}\|^{2}=\lambda\|\mathbf{x}\|^{2}$$

故$\lambda \geq 0$。同理，$A A^{T}$的特征值也全为非负数。

（2）$A A^{T}$与$A^{T} A$的非零特征值集合相同
证明：因为$r\left(A A^{T}\right)=r\left(A^{T}\right)=r(A)=r\left(A^{T} A\right)=r$。$A^{T} A$与对角矩阵相似，相似矩阵秩相同。对角矩阵的秩等于非零特征值数量。故$A A^{T}$的非零特征值数量等于$A^{T} A$的非零特征值数量，等于他们的秩。
设$\lambda$是$A^{T} A$的非零特征值，则存在非零向量$\mathbf{x}$，使得$A^{T} A \mathbf{x}=\lambda \mathbf{x}$。则有$A A^{T} A \mathbf{x}=\lambda A \mathbf{x}$。其中$A \mathbf{x}不等于零向量，$故$\lambda$也是$A A^{T}$的非零特征值。反之亦然。因此$A A^{T}$与$A^{T} A$具有相同的非零特征值。

（3）不妨设$A A^{T}$和$A^{T} A$的这$r$个非零特征值为$\sigma{1}^{2} \geq \cdots \geq \sigma{r}^{2}>0$，其中$\sigma{i}>0$。
设$\mathbf{v}{1}, \cdots, \mathbf{v}_{n} \in \mathbb{R}^{n}$为$n$阶实对称方阵$A^{T} A$的单位正交特征向量

$$A^{T} A\left(\mathbf{v}_{1} \cdots \mathbf{v}_{n}\right)=\left(\mathbf{v}_{1} \cdots \mathbf{v}_{n}\right)\left(\begin{array}{cccc} {\sigma_{1}^{2}} & {} & {} & {} \\ {} & {\ddots} & {} & {} \\ {} & {} & {\sigma_{r}^{2}} \\ {} & {} & {} & {0} \end{array}\right)$$

记$V=\left(\mathbf{v}{1}, \cdots, \mathbf{v}{n}\right)$，因为$V$为正交矩阵，有$V^{T} V=I{n}$。
注意到$A^{T} A \mathbf{v}{i}=\sigma{i}^{2} \mathbf{v}{i} \quad(1 \leq i \leq r)$
故$\mathbf{v}{i}^{T} A^{T} A \mathbf{v}{i}=\sigma{i}^{2} \mathbf{v}{i}^{T} \mathbf{v}{i}$，即$\left|A \mathbf{v}{i}\right|^{2}=\sigma{i}^{2}$。
令$\mathbf{u}{i}:=\frac{A \mathbf{v}{i}}{\sigma{i}} \in \mathbb{R}^{m}(1 \leq i \leq r)$，则$A A^{T} \mathbf{u}{i}=\sigma{i}^{2} \mathbf{u}_{i}$，并且

$$\mathbf{u}_{i}^{T} \mathbf{u}_{j}=\frac{\left(A \mathbf{v}_{i}\right)^{T}}{\sigma_{i}} \frac{A \mathbf{v}_{j}}{\sigma_{j}}=\frac{\mathbf{v}_{i}^{T}\left(A^{T} A \mathbf{v}_{j}\right)}{\sigma_{i} \sigma_{j}}=\frac{\sigma_{j}^{2} \mathbf{v}_{i}^{T} \mathbf{v}_{j}}{\sigma_{i} \sigma_{j}}=\frac{\sigma_{j}}{\sigma_{i}} \delta_{i j}=\delta_{i j}$$

故$\left{\mathbf{u}_{i} | 1 \leq i \leq r\right}$是$A A^{T}$的单位正交特征向量。
又有

$$A \mathbf{v}_{i}=\sigma_{i} \mathbf{u}_{i}, \quad A^{T} \mathbf{u}_{i}=\sigma_{i} \mathbf{v}_{i} \quad 1 \leq i \leq r$$

$\mathbf{u}{i}$在矩阵$A$的列空间里，$\mathbf{v}{i}$在矩阵$A$的行空间里，故
$\left{\mathbf{u}{1}, \cdots, \mathbf{u}{r}\right}$为$C(A)$的一组单位正交基
$\left{\mathbf{v}{1}, \cdots, \mathbf{v}{r}\right}$为$C(A^{T})$的一组单位正交基

奇异值分解的几何意义

一般地，秩为$r$的$m \times n$矩阵$A$有SVD：$A_{m \times n}=U \Sigma V^{T}$，则从$\mathbb{R}^{n}$到$\mathbb{R}^{m}$的线性变换$\mathbf{x} \mapsto A \mathbf{x}$可以看成是以下三步的复合：
（1）$\mathbb{R}^{n}$中的旋转$\mathbf{x} \mapsto V^{T} \mathbf{x}$
（2）$\mathbb{R}^{n}$中的向量$V^{T} \mathbf{x}$的前$r$个分量做伸缩，其余分量变为0：

$$V^{T} \mathbf{x} \mapsto \Sigma V^{T} \mathbf{x}$$

（3）再在$\mathbb{R}^{m}$中做旋转

$$\Sigma V^{T} \mathbf{x} \mapsto U \Sigma V^{T} \mathbf{x}$$

SVD与矩阵的四个基本子空间

设$A=U \Sigma V^{T}$是$m \times n$实矩阵$A$的奇异值分解，$r=r(A)$，则
$\ast$正交矩阵$U$的前$r$列是$C\left(A \right)$的一组标准正交基
$\ast$正交矩阵$U$的后$m-r$列是$N\left(A^{T} \right)$的一组标准正交基
$\ast$正交矩阵$V$的前$r$列是$C\left(A^{T} \right)$的一组标准正交基
$\ast$正交矩阵$V$的后$n-r$列是$N\left(A \right)$的一组标准正交基

SVD与图像压缩

设秩$r$的$m \times n$矩阵$A$的奇异值分解为

$$A=U \Sigma V^{T}=\sigma_{1} \mathbf{u}_{1} \mathbf{v}_{1}^{T}+\cdots+\sigma_{r} \mathbf{u}_{r} \mathbf{v}_{r}^{T}$$

其中$\sigma{1} \geq \sigma{2} \geq \cdots \geq \sigma{r}>0$
令$A{k}=\sigma{1} \mathbf{u}{1} \mathbf{v}{1}^{T}+\cdots+\sigma{k} \mathbf{u}{k} \mathbf{v}{k}^{T} \quad(1 \leq k<r)$
称为$A$的$k$阶逼近。特别地，$k=1$时，$A_{1}$是1阶逼近。

例如：一幅规格为$m \times n$像素的照片可用一个$m \times n$矩阵来存储。利用矩阵的奇异值分解，只需存储矩阵的奇异值$\sigma{i}$，奇异向量$\mathbf{u}{i}, \mathbf{v}{i}$的分量，总计$r \cdot(m+n+1)$个数据，而不是原始的$m \times n$个数据。通常$r \ll m, r \ll n$，则$r \cdot(m+n+1) \ll m \cdot n$。比值$\frac{m \cdot n}{r \cdot(m+n+1)}$称为图像的压缩比（其倒数称为数据压缩率）
若$\sigma{1}, \cdots \sigma{k}$远大于$\sigma{k+1}, \cdots \sigma{r}$，则$A{k} \approx A$图像不失真且压缩了存储量。对于较大的$k$，可以获得保真度较高的还原数据。而较小的$k$，可以获得较高的传输效率。

SVD与特征值

命题：设$|\lambda|_{\max }$是矩阵$A$的特征值的模长的最大值，则

$$\sigma_{1} \geq|\lambda|_{\max }, \sigma_{1} \geq\left|a_{i j}\right|, \quad \forall i, j$$

证明：设$A$有奇异值分解$A=U \Sigma V^{T}$，则对任意向量$\mathbf{x}$，有

$$\|A \mathbf{x}\|=\left\|U \Sigma V^{T} \mathbf{x}\right\|=\left\|\Sigma V^{T} \mathbf{x}\right\| \leq \sigma_{1}\left\|V^{T} \mathbf{x}\right\|=\sigma_{1}\|\mathbf{x}\|$$

特别地，若$A \mathbf{x}=\lambda \mathbf{x}$，其中$\mathbf{x}$为对应于$\lambda$的特征向量。则$|A \mathbf{x}|=|\lambda| \cdot|\mathbf{x}|$，故$\sigma{1} \geq|\lambda|$，特别有$\sigma{1} \geq|\lambda|{\max }$。
又若取$\mathbf{x}=(1,0, \cdots, 0)$，则$A \mathbf{x}$表示$A$的第一列向量，且$|A \mathbf{x}| \leq \sigma{1}|\mathbf{x}|=\sigma_{1}$，而

$$\left|a_{i 1}\right| \leq \sqrt{a_{11}^{2}+\cdots+a_{n 1}^{2}} \leq \sigma_{1}$$

同理，任何一列的某一个分量都有$\left|a{i j}\right| \leq \sigma{1}$，即矩阵的任意一个元素的绝对值都小于等于矩阵$A$的最大的奇异值。