奇异值分解¶

奇异值分解(Singular Value Decomposition, SVD)是一种重要的矩阵分解技术，在机器学习、推荐系统、自然语言处理等领域有广泛应用。

定义¶

假设有一个矩阵 $A$，其维度为 $m \times n$。那么 $A$ 的奇异值分解可以表示为：

\[ A = U \Sigma V^T \]

其中：

$U$ 是一个 $m \times m$ 的酉矩阵 (Unitary Matrix) (如果 $A$ 是实数矩阵，则 $U$ 是正交矩阵)。$U$ 的列向量被称为 $A$ 的左奇异向量 (Left Singular Vectors)。
$\Sigma$ 是一个 $m \times n$ 的非负实数对角矩阵。对角线上的元素 $\sigma_i = \Sigma_{ii}$ 被称为 $A$ 的奇异值 (Singular Values)。这些奇异值通常按降序排列，即 $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$，其中 $r = \text{rank}(A)$ 是矩阵 $A$ 的秩，其余的元素为0。如果 $m > n$，则 $\Sigma$ 的最后 $m-n$ 行为零。如果 $n > m$，则 $\Sigma$ 的最后 $n-m$ 列为零。
$V^T$ 是一个 $n \times n$ 的酉矩阵 (Unitary Matrix) (如果 $A$ 是实数矩阵，则 $V$ 是正交矩阵，$V^T$ 是 $V$ 的转置)。$V$ 的列向量被称为 $A$ 的右奇异向量 (Right Singular Vectors)。

一般而言，我们在机器学习中仅考虑实矩阵的情况

图示:

当 $m > n$ 时：

\[ \begin{bmatrix} \\ A \\ \\ \end{bmatrix}_{m \times n} = \begin{bmatrix} \\ U \\ \\ \end{bmatrix}_{m \times m} \begin{bmatrix} \sigma_1 & & \\ & \sigma_2 & \\ & & \ddots \\ & & & \sigma_n \\ 0 & \dots & & 0 \\ \vdots & & & \vdots \\ 0 & \dots & & 0 \end{bmatrix}_{m \times n} \begin{bmatrix} & V^T & \\ \end{bmatrix}_{n \times n} \]

当 $m < n$ 时：

\[ \begin{bmatrix} & A & \end{bmatrix}_{m \times n} = \begin{bmatrix} & U & \end{bmatrix}_{m \times m} \begin{bmatrix} \sigma_1 & & & 0 & \dots & 0 \\ & \sigma_2 & & \vdots & & \vdots \\ & & \ddots & 0 & \dots & 0 \\ & & & \sigma_m \end{bmatrix}_{m \times n} \begin{bmatrix} \\ V^T \\ \\ \end{bmatrix}_{n \times n} \]

核心思想¶

任何线性变换（由矩阵 A 表示）都可以分解为三个基本操作的序列：

旋转或反射 (VT)： 首先，它对输入空间进行一次旋转（或反射），将原始坐标轴对齐到一组新的正交轴上。这些新轴的方向由 V 的列向量（右奇异向量）给出。可以理解为找到了输入数据最“合适”的朝向。
缩放 (Σ)： 然后，沿着这些新的对齐轴，对数据进行独立的缩放。缩放的比例因子就是奇异值 σi。每个奇异值对应一个轴的拉伸或压缩程度。
另一次旋转或反射 (U)： 最后，它对经过缩放的数据在输出空间进行另一次旋转（或反射），将其对齐到最终的输出位置。这些最终轴的方向由 U 的列向量（左奇异向量）给出。

性质¶

SVD 具有许多重要的性质：

存在性和唯一性:
- 任何 $m \times n$ 的实数或复数矩阵都存在奇异值分解。
- 奇异值 $\sigma_i$ 是唯一的。
- 如果所有奇异值都是唯一的且大于零，那么左右奇异向量 $U$ 和 $V$ 在相差一个复数相位因子（对于实矩阵，则是相差符号因子 $\pm 1$）的意义下是唯一的。如果存在相同的奇异值，则对应的奇异向量张成的子空间是唯一的，但这些向量本身不是唯一的。
奇异值与特征值的关系:
- $A^T A$ 的特征值是 $\sigma_i^2$ (以及 $n-r$ 个零特征值)。$V$ 的列向量是 $A^T A$ 的特征向量。
  
  \[ A^T A = (U \Sigma V^T)^T (U \Sigma V^T) = V \Sigma^T U^T U \Sigma V^T = V (\Sigma^T \Sigma) V^T \]
  
  因此，$V$ 的列是 $A^T A$ 的特征向量，$\Sigma^T \Sigma$ 是一个 $n \times n$ 的对角矩阵，其对角元素为 $\sigma_i^2$。 * $A A^T$ 的特征值也是 $\sigma_i^2$ (以及 $m-r$ 个零特征值)。$U$ 的列向量是 $A A^T$ 的特征向量。
  
  \[ A A^T = (U \Sigma V^T) (U \Sigma V^T)^T = U \Sigma V^T V \Sigma^T U^T = U (\Sigma \Sigma^T) U^T \]
  
  因此，$U$ 的列是 $A A^T$ 的特征向量，$\Sigma \Sigma^T$ 是一个 $m \times m$ 的对角矩阵，其对角元素为 $\sigma_i^2$。 3. 秩 (Rank): * 矩阵 $A$ 的秩等于其非零奇异值的个数，即$ \text{rank}(A) = r $ 4. 矩阵范数 (Matrix Norms): * 矩阵的 Frobenius 范数可以用奇异值表示：
  
  \[ \|A\|_F = \sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n} |a_{ij}|^2} = \sqrt{\sum_{i=1}^{\text{min}(m,n)} \sigma_i^2} \]
- 矩阵的 谱范数 (2-范数) 等于最大的奇异值：
  
  \[ \|A\|_2 = \max_{\|x\|_2=1} \|Ax\|_2 = \sigma_1 \]
低秩逼近 (Low-Rank Approximation):
- SVD 最重要的应用之一是找到给定矩阵的最佳低秩逼近。如果我们将奇异值按降序排列 $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$，并选择前 $k$ 个最大的奇异值 ($k < r$)，以及对应的左右奇异向量，可以构造一个秩为 $k$ 的矩阵 $A_k$：
  
  \[ A_k = U_k \Sigma_k V_k^T \]
  
  其中 $U_k$ 是 $U$ 的前 $k$ 列，$\Sigma_k$ 是包含前 $k$ 个奇异值的 $k \times k$ 对角矩阵，$V_k^T$ 是 $V^T$ 的前 $k$ 行。 * Eckart-Young-Mirsky 定理: 矩阵 $A_k$ 是在 Frobenius 范数和谱范数意义下，秩不超过 $k$ 的矩阵中对 $A$ 的最佳逼近。
  
  \[ \min_{\text{rank}(B)=k} \|A - B\|_2 = \|A - A_k\|_2 = \sigma_{k+1} \]
  
  \[ \min_{\text{rank}(B)=k} \|A - B\|_F = \|A - A_k\|_F = \sqrt{\sum_{i=k+1}^{\text{min}(m,n)} \sigma_i^2} \]
四个基本子空间: SVD 提供了对矩阵 $A$ 的四个基本子空间的正交基：
- 列空间 (Column Space or Range) $\mathcal{R}(A)$: 由 $U$ 的前 $r$ 列张成。
- 左零空间 (Left Null Space or Cokernel) $\mathcal{N}(A^T)$: 由 $U$ 的后 $m-r$ 列张成。
- 行空间 (Row Space or Corange) $\mathcal{R}(A^T)$: 由 $V$ 的前 $r$ 列张成。
- 零空间 (Null Space or Kernel) $\mathcal{N}(A)$: 由 $V$ 的后 $n-r$ 列张成。