前言

参考：

《统计学习》—李航（蓝皮）

SVD（奇异值分解）

定义与定理

定义（奇异值分解） 矩阵的奇异值分解是指，将一个非零的 $m\times n$ 实矩阵 $A,A\in\mathbf{R}^{m\times n}$ ，表示为以下三个实矩阵乘积形式的运算，即进行矩阵的因子分解
::: align-center
$A=U\Sigma V^T$

:::
其中 $U$ 是 $m$ 阶正交矩阵（Orthogonal Matrix）， $V$ 是 $n$ 阶正交矩阵， $\Sigma$ 是由降序排列的非负对角线元素组成的 $m\times n$ 矩阵对角矩阵（Rectangular Diagonal Matrix），满足
::: align-center
$\begin{aligned} &UU^T=I\\ &VV^T=I\\ &\Sigma=diag(\sigma_1,\sigma_2,\cdots,\sigma_p)\\ &\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_p\ge 0\\ &p=\min(m,n) \end{aligned}$

:::
$U\Sigma V^T$ 称为矩阵 $A$ 的奇异值分解（Sigular Value Decomposition, SVD）， $\sigma_i$ 称为矩阵 $A$ 的奇异值（Singular Value）， $U$ 的列向量称为左奇异向量（Left Singular Vector）， $V$ 的列向量称为右奇异向量（Right Singular Vector）

注意奇异值分解不要求矩阵 $A$ 是方阵，事实上矩阵的奇异值分解可以看作是方阵的对角化的推广

任意给定一个实矩阵，它的奇异值分解一定存在，这里不证

紧奇异值分解与截断奇异值分解

上面定义中给出的奇异值分解
::: align-center
$A=U\Sigma V^T$

:::
又称为矩阵的完全奇异值分解（Full Singular Diagonal Decomposition）。实际常用的是奇异值分解的紧凑形式和截断形式。

紧凑奇异值分解是与原始矩阵等秩的奇异值分解
截断奇异值分解是比原始矩阵低秩的奇异值分解

在实际应用中，常常需要对矩阵的数据进行压缩，将其近似表示，奇异值分解提供了一种方法。后面将要叙述，奇异值分解分解是在平方损失（弗罗贝尼乌斯范数）意义下对矩阵的最优近似。紧奇异值分解对应着无损压缩，截断奇异值分解对应着有损压缩

紧奇异值分解

定义设有 $m\times n$ 实矩阵 $A$ ，其秩为 $rank(A)=r,r\le\min(m,n)$ ，则称 $U_r\Sigma_rV^T_r$ 为 $A$ 的紧凑奇异值分解（Compact Singular Decomposition），即
::: align-center
$A=U_r\Sigma_rV^T_r$

:::
其中 $U_r$ 是 $m\times r$ 矩阵， $V_r$ 是 $n\times r$ 矩阵， $\Sigma_r$ 是 $r$ 阶对角矩阵；矩阵 $U_r$ 由完全奇异值分解中 $U$ 的前 $r$ 列、矩阵 $V_r$ 由 $V$ 的前 $r$ 列、矩阵 $\Sigma_r$ 由 $\Sigma$ 的前 $r$ 个对角线元素得到。紧奇异值分解的对角矩阵 $\Sigma_r$ 的秩与原始矩阵 $A$ 的秩相等

截断奇异值分解

在矩阵的奇异值分解中，只取最大的 $k$ 个奇异值（ $k 为矩阵的秩）对应的部分，就得到矩阵的截断奇异值分解。实际应用中提到矩阵的奇异值分解时，通常指截断奇异值分解$

定义设 $A$ 为 $m\times n$ 实矩阵，其秩 $rank(A)=r$ ，且 $0，则称U_k\Sigma_kV_k^T为矩阵A的截断奇异值分解（Truncated Singular Value Decomposition） ::: align-center A\approx U_k\Sigma_kV_k^T$

:::
其中 $U_k$ 是 $m\times k$ 矩阵， $V_k$ 是 $n\times k$ 矩阵， $\Sigma_k$ 是 $k$ 阶对角矩阵；矩阵 $U_k$ 由完全奇异值分解中 $U$ 的前 $k$ 列、矩阵 $V_k$ 由 $V$ 的前 $k$ 列、矩阵 $\Sigma_k$ 由 $\Sigma$ 的前 $k$ 个对角线元素得到。对角矩阵 $\Sigma_k$ 的秩比原始矩阵 $A$ 的秩低

几何解释

对矩阵 $A$ 进行奇异值分解，得到 $A=U\Sigma V^T$ ， $V,U$ 都是正交矩阵，所以 $V$ 的列向量 $v_1,v_2,\cdots,v_n$ 构成 $\mathbf{R}^n$ 空间的一组标准正交基，表示 $\mathbf{R}^n$ 中的正交坐标系旋转或反射变换， $U$ 同理； $\Sigma$ 是非负对角矩阵，表示 $\mathbf{R}^n$ 中的原始正交坐标系坐标轴的缩放变换

任意一个向量 $x\in\mathbf{R}^n$ ，经过基于 $A=U\Sigma V^T$ 的线性变换，等价于经过坐标系的旋转或反射变换 $V^T$ ，坐标轴的缩放变换 $\Sigma$ ，以及坐标轴的旋转或反射变换 $U$ ，得到向量 $Ax\in\mathbf{R}^m$
奇异值分解的几何解释.jpg

可以知道旋转、反射、缩放变换都是基本的线性变换，这也保证了奇异值分解一定是存在的

主要性质

（1）设矩阵 $A$ 的奇异值分解为 $A=U\Sigma V^T$ ，则以下关系成立：
::: align-center
$\begin{aligned} &A^TA=(U\Sigma V^T)^T(U\Sigma V^T)=V(\Sigma^T\Sigma)V^T\\ &AA^T=(U\Sigma V^T)(U\Sigma V^T)^T=U(\Sigma\Sigma^T)U^T \end{aligned}$

:::
又因为 $U,V$ 均为正交矩阵， $U^T=U^{-1},V^T=V^{-1}$ ，也就是说， $A^TA,AA^T$ 的特征分解（谱分解）均存在，且可以由矩阵 $A$ 的奇异值分解的矩阵表示， $V$ 的列向量是 $A^TA$ 的特征向量， $U$ 的列向量是 $AA^T$ 的列向量， $\Sigma$ 是 $A^TA,AA^T$ 的特征值的平方根

（2）在矩阵 $A$ 的奇异值分解中，奇异值、左奇异向量和右奇异向量之间存在对应关系
由 $A=U\Sigma V^T$ 易知
::: align-center
$AV=U\Sigma$

:::
比较这一等式两端的 $j$ 列，得到
::: align-center
$Av_j=\sigma_ju_j,j=1,2,\cdots,n$

:::
这是矩阵 $A$ 的右奇异向量和奇异值、左奇异向量的关系

类似地，由
::: align-center
$A^TU=V\Sigma^T$

:::
得到
::: align-center
$\begin{aligned} &A^Tu_j=\sigma_jv_j,j=1,2,\cdots,n\\ &A^Tu_j=0,j=n+1,n+2,\cdots,m \end{aligned}$

:::
这是矩阵 $A$ 的左奇异向量和奇异值、右奇异向量的关系

（3）矩阵 $A$ 的奇异值分解中，奇异值 $\sigma_1,\sigma_2,\cdots,\sigma_n$ 是唯一的，而矩阵 $U$ 和 $V$ 不是唯一的

（4）矩阵 $A$ 和 $\Sigma$ 的秩相等，等于正奇异值 $\sigma_i$ 的个数 $r$ （包含重复的奇异值）

（5）矩阵 $A$ 的 $r$ 个右奇异向量构成 $A$ 的行空间 $\mathcal{R}(A^T)$ 的一组标准正交基。矩阵 $A$ 的 $n-r$ 个右奇异向量 $v_{r+1},v_{r+2},\cdots,v_n$ 构成 $A$ 的零空间 $\mathcal{N}(A)$ 的一组标准正交基
矩阵 $A$ 的 $r$ 个左奇异向量 $u_1,u_2,\cdots,u_r$ 构成 $A$ 的列空间 $\mathcal{R}(A)$ 的一组标准正交基，矩阵 $A$ 的 $m-r$ 个左奇异向量 $u_{r+1},u_{r+2},\cdots,u_{m}$ 构成 $A$ 的左零空间 $\mathcal{N}(A^T)$ 的一组标准正交基

笔者：参考这篇文章，首先矩阵 $A$ 的r个右奇异向量来自 $A^TA$ 的正交特征向量，而 $A^TA$ 的这些正交特征向量由于 $\mathcal{R}(A^TA)=\mathcal{R}(A^T)$ 张成 $A$ 的行空间，维数即行秩为 $r$ ，类似地可得为何r个左奇异向量张成 $A$ 的 $r$ 维列空间，之后由定义域、陪域与行、列空间维度的关系得到零空间和左零空间的维数分别为 $n-r,m-r$ ，这就是剩下的 $n-r$ 个右奇异向量和 $m-r$ 个左奇异向量张成的空间

过奇异值分解， $U$ 由 $A$ 的列空间的正交基和左零空间的正交基组成，这有利于更好的理解数据。同时 $\Sigma$ 由 $A$ 的奇异值由大到小排列组成，这有利于我们保留主干信息而压缩次要信息（截断奇异值分解）

奇异值分解的计算

（1）首先求 $A^TA$ 的特征值和特征向量
计算对称矩阵 $W=A^TA$
求解特征方程
::: align-center
$(W-\lambda I)x=0$

:::
得到特征值 $\lambda_j$ ，并将特征值由大到小排列
::: align-center
$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n\ge0$

:::
将特征值 $\lambda_j(j=1,2,\cdots,n)$ 代入特征方程求得对应的特征向量
（2）求 $n$ 阶正交矩阵 $V$
将特征向量单位化，得到单位特征向量 $v_1,v_2\cdots,v_n$ ，构成 $n$ 阶正交矩阵 $V$
::: align-center
$V=\begin{bmatrix}v_1&v_2&\cdots&v_n\end{bmatrix}$

:::
（3）求 $m\times n$ 对角矩阵 $\Sigma$
计算 $A$ 的奇异值
::: align-center
$\sigma_j=\sqrt{\lambda_j},j=1,2,\cdots,n$

:::
构造 $m\times n$ 矩形对角矩阵 $\Sigma$ ，主对角线元素是奇异值，其余元素是零
::: align-center
$\Sigma=diag(\sigma_1,\sigma_2,\cdots,\sigma_n)$

:::
（4）求 $m$ 阶正交矩阵 $U$
对 $A$ 的前 $r$ 个奇异值，令
::: align-center
$u_j=\frac{1}{\sigma_j}Av_j,j=1,2,\cdots,r$

:::
得到
::: align-center
$U_1=\begin{bmatrix}u_1&u_2&\cdots&u_r\end{bmatrix}$

:::
求 $A^T$ 零空间（即 $A$ 的左零空间）的一组标准正交基 $\{u_{r+1},u_{r+2},\cdots,u_m\}$ ，令
::: align-center
$U_2=\begin{bmatrix}u_{r+1}&u_{r+2},\cdots&u_m\end{bmatrix}$

:::
并令
::: align-center
$U=\begin{bmatrix}U_1&U_2\end{bmatrix}$

:::
（5）得到奇异值分解
::: align-center
$A=U\Sigma V^T$

:::

奇异值分解与矩阵近似

暂无计划整理