奇异值分解 SVD

1. SVD 的定义和一些重要性质

任何一个 $m \times n$ 的实数矩阵 $\boldsymbol{A}$ 都可以分解成 $\boldsymbol{A} = \boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^T$ 的形式。其中 $\boldsymbol{U}$ 和 $\boldsymbol{V}$ 分别是 $m \times m$ 和 $n \times n$ 的正交矩阵。$\boldsymbol{\Sigma}$ 则是一个对角线元素为 $\sigma_i$ 的 $m \times n$ 的对角矩阵，$\boldsymbol{\Sigma}$ 只有对角线上的 $p$ 个元素有值 $p = \text{min}(m,n)$ 其余全为 0。即， $$ \begin{equation}\label{func_svd} \boldsymbol{U}^T \boldsymbol{A}\boldsymbol{V} = \boldsymbol{\Sigma} = \text{diag}\left(\sigma_1, \cdots, \sigma_p\right), \qquad p = \text{min}(m, n), \qquad \sigma_1 ≥ \sigma_2 ≥ \cdots ≥ \sigma_p ≥ 0 \end{equation} $$ 上式中，$\sigma_i$ 被称为矩阵 $\boldsymbol{A}$ 的奇异值(singular value)。构成矩阵 $\boldsymbol{U}$ 的列向量 $u_i$ 是矩阵 $\boldsymbol{A}$ 的左奇异向量(left singular vector)，矩阵 $\boldsymbol{V}$ 的各列向量 $v_i$ 则是 $\boldsymbol{A}$ 的右奇异向量(right singular vector)。这就是著名的奇异值分解 Singular Value Decomposition，在现代的科学计算中，它几乎无处不在。

根据 SVD 分解的定义，可以直接写出奇异值与左右奇异向量的关系 $\boldsymbol{A}\boldsymbol{v}_i = \sigma_i \boldsymbol{u}_i, \boldsymbol{A}^T\boldsymbol{u}_i = \sigma_i \boldsymbol{v}_i$。我们也可以推出，$\boldsymbol{A}^T\boldsymbol{A}\boldsymbol{v}_i = \sigma_i^2 \boldsymbol{v}_i$, $\boldsymbol{A}\boldsymbol{A}^T\boldsymbol{u}_i = \sigma_i^2 \boldsymbol{u}_i$。这个推论实际反映了奇异值与特征值之间的关系：矩阵 $\boldsymbol{A}$ 的奇异值及对应的左右奇异向量，分别是矩阵 $\boldsymbol{A}\boldsymbol{A}^T$ 和 $\boldsymbol{A}^T\boldsymbol{A}$ 的特征值的平方和特征向量。此外，SVD 分解还可以写成 $\boldsymbol{A} = \sum_{i=1}^p \sigma_i \boldsymbol{u}_i \boldsymbol{v}_i^T$ 的形式。