奇异值分解SVD

1. SVD 定理

1.1 定理表述

设 $A$ 为 $m\times n$ 实矩阵，$r=r(A)$，则存在正交矩阵 $U$（$m\times m$）和正交矩阵 $V$（$n\times n$），使得：

$A=U\Sigma V^T$

其中 $\Sigma =\left(\begin{array}{cc}D& O\\ O& O\end{array}\right)$，$D=\text{diag}({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r)$，${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0$。

${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r$ 称为 $A$ 的奇异值。

1.2 瘦型 SVD

$A=U_r{\Sigma }_r{V}_r^T$

其中 $U_r$ 为 $m\times r$，${\Sigma }_r$ 为 $r\times r$，$V_r$ 为 $n\times r$。

1.3 证明思路

1. $A^{T}A$ 为 $n$ 阶实对称半正定矩阵，可正交对角化：$A^{T}A=V{\Lambda }^2{V}^T$
2. 设 $\Lambda =\text{diag}({\sigma }_1,\dots ,{\sigma }_r,0,\dots ,0)$，${\sigma }_i>0$
3. 令 $U_r=A{V}_r{\Sigma }_r^{-1}$，可验证 $U_r^T{U}_r=I_r$
4. 扩充 $U_r$ 为正交矩阵 $U$，即得 $A=U\Sigma V^T$

2. 奇异值的计算

2.1 计算步骤

1. 计算 $A^{T}A$（$n\times n$ 实对称半正定矩阵）
2. 求 $A^{T}A$ 的特征值 ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n\ge 0$
3. 奇异值 ${\sigma }_i=\sqrt{{\lambda }_i}$（$i=1,2,\dots ,r$）
4. 求 $A^{T}A$ 的属于 ${\lambda }_i$ 的标准正交特征向量 ${\mathbf{v}}_i$，构成 $V$
5. 计算 ${\mathbf{u}}_i=\frac{A{\mathbf{v}}_i}{{\sigma }_i}$（$i=1,\dots ,r$），扩充为正交矩阵 $U$

2.2 也可以用 $A{A}^T$

$A{A}^T$ 的非零特征值与 $A^{T}A$ 的非零特征值相同，对应的特征向量构成 $U$ 的前 $r$ 列。

2.3 完整示例

求 $A=\left(\begin{array}{cc}1& 1\\ 0& 1\\ 1& 0\end{array}\right)$ 的 SVD。

步骤1：

$A^{T}A=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$

步骤2：$|A^{T}A-\lambda I|=(2-\lambda {)}^2-1=(\lambda -1)(\lambda -3)$

${\lambda }_1=3$，${\lambda }_2=1$

${\sigma }_1=\sqrt{3}$，${\sigma }_2=1$

步骤3：$A^{T}A$ 的特征向量

${\lambda }_1=3$：${\mathbf{v}}_1=\frac{1}{\sqrt{2}}(1,1{)}^T$

${\lambda }_2=1$：${\mathbf{v}}_2=\frac{1}{\sqrt{2}}(1,-1{)}^T$

$V=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

步骤4：

${\mathbf{u}}_1=\frac{A{\mathbf{v}}_1}{{\sigma }_1}=\frac{1}{\sqrt{3}}\cdot \frac{1}{\sqrt{2}}\left(\begin{array}{c}2\\ 1\\ 1\end{array}\right)=\frac{1}{\sqrt{6}}\left(\begin{array}{c}2\\ 1\\ 1\end{array}\right)$

${\mathbf{u}}_2=\frac{A{\mathbf{v}}_2}{{\sigma }_2}=\frac{1}{\sqrt{2}}\cdot \frac{1}{\sqrt{2}}\left(\begin{array}{c}0\\ -1\\ 1\end{array}\right)=\frac{1}{2}\left(\begin{array}{c}0\\ -1\\ 1\end{array}\right)$

扩充 ${\mathbf{u}}_3$ 使 $U$ 为正交矩阵：${\mathbf{u}}_3=\frac{1}{\sqrt{3}}(1,-1,-1{)}^T$

$U=\left(\begin{array}{ccc}\frac{2}{\sqrt{6}}& 0& \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{6}}& -\frac{1}{2}& -\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{6}}& \frac{1}{2}& -\frac{1}{\sqrt{3}}\end{array}\right)$

$\Sigma =\left(\begin{array}{cc}\sqrt{3}& 0\\ 0& 1\\ 0& 0\end{array}\right)$

3. SVD 的几何意义

3.1 线性变换的分解

$A=U\Sigma V^T$ 表示线性变换 $A$ 可分解为：

1. 旋转/反射 $V^T$：在输入空间中旋转
2. 伸缩 $\Sigma$：沿坐标轴方向伸缩（奇异值为伸缩因子）
3. 旋转/反射 $U$：在输出空间中旋转

3.2 像的几何描述

$A$ 将单位球 $\{\mathbf{x}\mid \Vert \mathbf{x}\Vert =1\}$ 映射为椭球面，椭球的半轴长度为奇异值 ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r$。

3.3 低秩近似

Eckart-Young 定理：在 Frobenius 范数（或谱范数）下，$A$ 的最佳 $k$ 秩近似为：

$A_k={\sum }_{i=1}^k{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$

近似误差：$\Vert A-A_k{\Vert }_F=\sqrt{{\sigma }_{k+1}^2+\cdots +{\sigma }_r^2}$

4. SVD 的重要性质

4.1 奇异值的性质

1. ${\sigma }_{\max }(A)=\Vert A{\Vert }_2$（谱范数）
2. ${\sigma }_{\min }(A)={\min }_{\mathbf{x}\ne 0}\frac{\Vert A\mathbf{x}\Vert }{\Vert \mathbf{x}\Vert }$（$A$ 列满秩时）
3. $\kappa (A)=\frac{{\sigma }_{\max }}{{\sigma }_{\min }}$（条件数）
4. $\Vert A{\Vert }_F^2={\sigma }_1^2+{\sigma }_2^2+\cdots +{\sigma }_r^2$
5. $|A|={\sigma }_1{\sigma }_2\cdots {\sigma }_n$（$A$ 为方阵时）

4.2 与特征值的关系

• $A^{T}A$ 的特征值为 ${\sigma }_1^2,{\sigma }_2^2,\dots ,{\sigma }_r^2,0,\dots ,0$
• $A{A}^T$ 的特征值为 ${\sigma }_1^2,{\sigma }_2^2,\dots ,{\sigma }_r^2,0,\dots ,0$
• 若 $A$ 为实对称矩阵，奇异值等于特征值的绝对值

4.3 子空间关系

• $V$ 的前 $r$ 列：$\text{Row}(A)$ 的标准正交基
• $V$ 的后 $n-r$ 列：$N(A)$ 的标准正交基
• $U$ 的前 $r$ 列：$\text{Col}(A)$ 的标准正交基
• $U$ 的后 $m-r$ 列：$N(A^T)$ 的标准正交基

5. SVD 的应用

5.1 矩阵的伪逆

$A^{+}=V{\Sigma }^{+}{U}^T$

其中 ${\Sigma }^{+}=\text{diag}(1/{\sigma }_1,\dots ,1/{\sigma }_r,0,\dots ,0)$。

5.2 最小二乘解

$\min \Vert Ax-b\Vert$ 的最小范数解为 $x=A^{+}b$。

5.3 矩阵的低秩近似

截断 SVD：$A_k=U_k{\Sigma }_k{V}_k^T$，用于数据压缩。

5.4 图像压缩

将图像矩阵做 SVD，保留前 $k$ 个奇异值，实现有损压缩。压缩比约为 $\frac{mn}{k(m+n+1)}$。

5.5 降噪

信号中的噪声通常对应较小的奇异值，截断小奇异值可以实现降噪。