十五、奇异值分解（SVD）

奇异值分解 (Singular Value Decomposition, SVD)，一种数据降维方法（常用于图像压缩），统计学习中，主成分分析（PCA）等降维方法都可表示为奇异值分解的形式。

定义¶

有非零的 $m \times n$ 实矩阵 $A$，即 $A \in R^{m \times n}$。将 $A$ 表示为三个矩阵乘积形式的奇异值分解：

$$ A = U\Sigma V^T $$

其中：
- $U$ 为 $m \times m$ 正交矩阵（$UU^T = I$）
- $\Sigma$ 为 $m \times n$ 对角矩阵，其对角线元素 $\sigma_i$ 满足 $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$，$r = \min(m,n)$
- $V$ 为 $n \times n$ 正交矩阵（$VV^T = I$）

其中 $\sigma_i$ 称为奇异值，$U$ 的列向量称为左奇异向量，$V$ 的列向量称为右奇异向量。

注意：非零矩阵 $A$ 的奇异值分解一定存在且不唯一。

任务：证明非零矩阵 $A$ 的 SVD 一定存在。¶

证明思路三步：¶

确定 $V$ 和 $\Sigma$
构造正交矩阵 $U$
验证 $U\Sigma V^T = A$

对于任意非零矩阵 $A \in \mathbb{R}^{m \times n}$，考虑矩阵 $A^TA$，这是一个 $n \times n$ 的对称矩阵，因此存在 $n$ 个正交的特征向量 $v_1, v_2, \ldots, v_n$，对应的特征值为 $\lambda_1, \lambda_2, \ldots, \lambda_n$。

将特征值按降序排列：$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$。

定义奇异值 $\sigma_i = \sqrt{\lambda_i}$，其中 $i = 1, 2, \ldots, r$，$r$ 为矩阵 $A$ 的秩。

对于 $i = 1, 2, \ldots, r$，定义 $u_i = \frac{1}{\sigma_i}Av_i$。

可以证明向量 $u_1, u_2, \ldots, u_r$ 是正交的，可以将其扩充为 $\mathbb{R}^m$ 的一组标准正交基 $u_1, u_2, \ldots, u_m$。

类似地，向量 $v_1, v_2, \ldots, v_n$ 构成 $\mathbb{R}^n$ 的一组标准正交基。

令 $U = [u_1, u_2, \ldots, u_m]$，$V = [v_1, v_2, \ldots, v_n]$，$\Sigma = \text{diag}(\sigma_1, \sigma_2, \ldots, \sigma_r, 0, \ldots, 0)$。

则有 $A = U\Sigma V^T$。

紧奇异值分解和截断奇异值分解¶

紧奇异值分解：¶

设矩阵 $A \in \mathbb{R}^{m \times n}$，$\text{rank}(A) = r$，则 $U \in \mathbb{R}^{m \times r}$，$\Sigma \in \mathbb{R}^{r \times r}$，$V \in \mathbb{R}^{n \times r}$ 为 $A$ 的紧奇异值分解（compact singular value decomposition）

$$ A = U\Sigma V^T $$

其中 $U$ 和 $V$ 的列向量分别是 $A$ 的 $r$ 个左奇异向量和右奇异向量，$\Sigma$ 是由 $r$ 个非零奇异值组成的对角矩阵。

截断奇异值分解：¶

设矩阵 $A \in \mathbb{R}^{m \times n}$，$\text{rank}(A) = r$，取 $k < r$，则 $U_k \in \mathbb{R}^{m \times k}$，$\Sigma_k \in \mathbb{R}^{k \times k}$，$V_k \in \mathbb{R}^{n \times k}$ 为 $A$ 的截断奇异值分解（truncated singular value decomposition）

$$ A_k = U_k\Sigma_k V_k^T $$

其中：
- $k < r$
- $A_k$ 是 $A$ 的最佳秩-$k$ 近似矩阵
- $\text{rank}(A_k) = k$

SVD 提供了一种数据压缩的方式，其中，紧 SVD 去除了零奇异值对应的项；截断 SVD 通过保留前 $k$ 个最大奇异值实现降维。¶

SVD的几何解释¶

SVD将一个线性变换分解为三个简单的变换：

旋转/反射变换：由 $V^T$ 表示，将输入空间中的向量旋转或反射
缩放变换：由 $\Sigma$ 表示，沿着各个主轴方向进行缩放，缩放因子为奇异值
旋转/反射变换：由 $U$ 表示，将缩放后的向量在输出空间中旋转或反射

具体来说，对于线性变换 $T: x \rightarrow Ax$，其中 $A \in \mathbb{R}^{m \times n}$：

$V$ 的列向量 $\{v_1, v_2, \ldots, v_n\}$ 构成 $\mathbb{R}^n$ 中的一组标准正交基
$U$ 的列向量 $\{u_1, u_2, \ldots, u_m\}$ 构成 $\mathbb{R}^m$ 中的一组标准正交基
奇异值 $\sigma_1, \sigma_2, \ldots, \sigma_r$ 表示在各个主方向上的缩放因子

因此，任何矩阵 $A$ 所表示的线性变换都可以理解为：先通过 $V^T$ 进行旋转，然后通过 $\Sigma$ 进行缩放，最后通过 $U$ 进行旋转。

SVD的主要性质¶

$A$ 的奇异值分解存在且不唯一：
- $A = U\Sigma V^T$
- $A^TA = V\Sigma^T\Sigma V^T$
- $AA^T = U\Sigma\Sigma^T U^T$
- 奇异值、左奇异向量与右奇异向量之间存在如下关系：
- $Av_j = \sigma_j u_j$, $j = 1, 2, ..., r$
- $A^Tu_j = \sigma_j v_j$, $j = 1, 2, ..., r$
- 其中 $r = \text{rank}(A)$
矩阵$A$的奇异值分解中，奇异值、左奇异向量、右奇异向量之间的对应关系：

$r$个非零奇异值$\sigma_1, \sigma_2, ..., \sigma_r$与$A^TA$（或$AA^T$）的非零特征值的平方根对应
$r$个左奇异向量$u_1, u_2, ..., u_r$构成$A$的列空间$R(A)$的一组标准正交基
$r$个右奇异向量$v_1, v_2, ..., v_r$构成$A$的行空间$R(A^T)$的一组标准正交基
$n-r$个右奇异向量$v_{r+1}, v_{r+2}, ..., v_n$构成$A$的零空间$N(A)$的一组标准正交基
$m-r$个左奇异向量$u_{r+1}, u_{r+2}, ..., u_m$构成$A$的左零空间$N(A^T)$的一组标准正交基

矩阵$A$和$A^T$的秩相等，等于非零奇异值的个数$r$。
矩阵$A$的奇异值是$A^TA$（或$AA^T$）的特征值的平方根，按降序排列：$\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$。

SVD过程详解¶

给定 $m \times n$ 矩阵 $A$，SVD过程如下：¶

(1) 求解 $A^TA$ 的特征值和特征向量¶

计算 $A^TA$，这是一个 $n \times n$ 的对称矩阵
求解特征方程 $\det(A^TA - \lambda I) = 0$，得到特征值
将特征值按降序排列：$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$
求解对应的特征向量 $v_1, v_2, \ldots, v_n$

(2) 求 $n \times n$ 正交矩阵 $V$¶

特征向量 $v_1, v_2, \ldots, v_n$ 构成正交矩阵 $V = [v_1, v_2, \ldots, v_n]$
这些特征向量是 $A$ 的右奇异向量

(3) 求 $m \times n$ 对角阵 $\Sigma$¶

计算 $A$ 的奇异值 $\sigma_i = \sqrt{\lambda_i}$，$i=1,2,\ldots,r$，其中 $r$ 是矩阵 $A$ 的秩
构造 $m \times n$ 对角阵 $\Sigma$，对角线元素为 $\sigma_1, \sigma_2, \ldots, \sigma_r, 0, \ldots, 0$
$\Sigma = \text{diag}(\sigma_1, \sigma_2, \ldots, \sigma_r, 0, \ldots, 0)$

(4) 求 $m \times m$ 正交矩阵 $U$¶

对 $j=1,2,\ldots,r$，计算 $u_j = \frac{1}{\sigma_j}Av_j$
将 $u_1, u_2, \ldots, u_r$ 扩充为 $\mathbb{R}^m$ 的一组标准正交基 $u_1, u_2, \ldots, u_m$
构造正交矩阵 $U = [u_1, u_2, \ldots, u_m]$

(5) 得到奇异值分解 $A = U\Sigma V^T$¶

注意：在实际计算中，当矩阵规模较大时，通常会根据具体情况选择计算 $A^TA$ 或 $AA^T$ 的特征值分解，以减少计算量。

Frobenius Norm¶

设矩阵 $A \in \mathbb{R}^{m \times n}$，$A = [a_{ij}]_{m \times n}$，定义矩阵 $A$ 的弗罗贝尼乌斯范数为

$$ \|A\|_F = \left( \sum_{i=1}^m \sum_{j=1}^n |a_{ij}|^2 \right)^{\frac{1}{2}} $$

弗罗贝尼乌斯范数具有以下性质：
1. $\|A\|_F \geq 0$，当且仅当 $A = 0$ 时等号成立
2. $\|\alpha A\|_F = |\alpha| \|A\|_F$，其中 $\alpha$ 为标量
3. $\|A + B\|_F \leq \|A\|_F + \|B\|_F$
4. $\|A\|_F = \|A^T\|_F$
5. $\|A\|_F = \sqrt{\text{tr}(A^TA)}$，其中 $\text{tr}(\cdot)$ 表示矩阵的迹

矩阵的范数与近似¶

引理¶

设矩阵 $A \in \mathbb{R}^{m \times n}$，$\sigma_1, \sigma_2, \ldots, \sigma_r$ 为 $A$ 的非零奇异值，则：

$$ \|A\|_F = \left( \sum_{i=1}^r \sigma_i^2 \right)^{\frac{1}{2}} $$

证明：¶

因为 $A = U\Sigma V^T$，且正交变换不改变弗罗贝尼乌斯范数，所以：

$$ \|A\|_F = \|U\Sigma V^T\|_F = \|\Sigma\|_F = \left( \sum_{i=1}^r \sigma_i^2 \right)^{\frac{1}{2}} $$

矩阵的最优近似¶

Eckart-Young定理¶

设矩阵 $A \in \mathbb{R}^{m \times n}$，秩 $\text{rank}(A) = r$，设 $\mathcal{M}_k$ 为 $\mathbb{R}^{m \times n}$ 中所有秩不超过 $k$ 的矩阵集合，其中 $k \leq r$，则：

$$ \min_{X \in \mathcal{M}_k} \|A - X\|_F = \|A - A_k\|_F = \sqrt{\sigma_{k+1}^2 + \sigma_{k+2}^2 + \cdots + \sigma_r^2} $$

称 $A_k$ 为 $A$ 的最佳秩-$k$ 近似。

特别地，若 $A = U\Sigma V^T$ 为 $A$ 的奇异值分解，其中：

$$ \Sigma = \begin{bmatrix} \Sigma_r & 0 \\ 0 & 0 \end{bmatrix}, \quad \Sigma_r = \begin{bmatrix} \sigma_1 & & 0 \\ & \ddots & \\ 0 & & \sigma_r \end{bmatrix} $$

则 $A$ 的最佳秩-$k$ 近似为：

$$ A_k = U_k \Sigma_k V_k^T $$

其中 $U_k$ 包含 $U$ 的前 $k$ 列，$\Sigma_k$ 包含 $\Sigma$ 的前 $k$ 个奇异值，$V_k$ 包含 $V$ 的前 $k$ 列。

因此：

$$ \min_{X \in \mathcal{M}_k} \|A - X\|_F = \sqrt{\sigma_{k+1}^2 + \sigma_{k+2}^2 + \cdots + \sigma_r^2} $$

矩阵的外积展开式¶

矩阵的奇异值分解 $A = U\Sigma V^T$ 也可以由列向量形式表示。

将 $U$、$\Sigma$、$V^T$ 按列分块，即：

$$ U = [u_1, u_2, \ldots, u_m], \quad \Sigma = \text{diag}(\sigma_1, \sigma_2, \ldots, \sigma_r, 0, \ldots, 0), \quad V^T = [v_1^T, v_2^T, \ldots, v_n^T] $$

则：

$$ A = U\Sigma V^T = \sum_{i=1}^r \sigma_i u_i v_i^T $$

称为矩阵 $A$ 的外积展开式。其中，$u_i v_i^T$ 为 $m \times n$ 矩阵，秩为1。

结论¶

设矩阵 $A \in \mathbb{R}^{m \times n}$，$A = \sum_{i=1}^r \sigma_i u_i v_i^T$，则 $A$ 的秩为 $r$，且 $A_k = \sum_{i=1}^k \sigma_i u_i v_i^T$ 是矩阵 $A$ 在秩不超过 $k$ 的矩阵集合中的最优近似，其中 $k \leq r$。

注：本文使用Qwen转换自本人的统计学习方法笔记。