奇异值分解(SVD)

奇异值分解(SVD)是一种矩阵因子分解方法。任意一个m*n的矩阵，都可以表示为三个矩阵的乘积(因子分解)的形式，分别是m阶正交矩阵、由降序排列的非负的对角线元素组成的m*n矩阵和n阶正交矩阵，称为该矩阵的奇异值分解。矩阵的奇异值分解一定存在，但不唯一。奇异值分解可以看作出矩阵数据压缩的一种方法。即用因子分解的方式近似地表示原始矩阵，这种矩阵在平方损失意义下的最优近似。

一、奇异值分解的定义与性质

矩阵的奇异值分解是指，将一个非零的m*n实矩阵 $A$ ，表示为以下三个实矩阵乘积形式的运算，即进行矩阵的因子分解
$A =U\Sigma V^T$
其中U是m阶正交矩阵，V是n阶正交矩阵， $\Sigma$ 是由降序排列的非负的对角元素组成的 $m\*n$ 的矩形对角矩阵
$\begin{aligned} UU^T = I \\ VV^r=T = I \\ \Sigma = diag(\sigma_1,\sigma_2,\dots,\sigma_p) \\ \sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_p \ge 0 \\ p = min(m,n) \end{aligned}$
$U\Sigma V^T$ 称为矩阵的奇异值分解， $\sigma_i$ 称为矩阵A的奇异值, $U$ 的列向量称为左奇异向量， $V$ 的列向量成为右奇异向量

(1)紧奇异值分解与截断奇异值分解

紧凑奇异值分解是与原始矩阵等秩的奇异值分解，截断奇异值分解是比原始矩阵降低秩的奇异值分解。在实际应用中，常常需要对矩阵的数据进行压缩，将其近似表示，奇异值分解提供了一种方法。奇异值分解是在平方损失意义下对矩阵的最优近似。紧奇异值分解对应着无损压缩，截断奇异值分解对应着有损压缩

(a)紧奇异值分解

设有 $m*n$ 实矩阵A，其秩为rank(A) = r, $r \le min(m,n)$ ，则称 $U_r\Sigma_rV_r^T$ 为A的紧奇异值分解，即
$A = U_r\Sigma_rV_r^T$
其中 $U_r$ 是 $m*r$ 矩阵， $V_r$ 是 $n*r$ 矩阵， $\Sigma_r$ 是r阶对角矩阵，矩阵 $U_r$ 由完全奇异分解中的前r列，矩阵 $V_r$ 由V的前r列，矩阵 $\Sigma_r$ 由 $\Sigma$ 的前r个对角线元素得到，紧奇分解的对角矩阵 $\Sigma_r$ 的秩与原始矩阵A的秩相等

(b)截断奇异值分解

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

设A为 $m*n$ 实矩阵，其秩rank(A)=r,且， $0 < k < r$ ，则称 $U_k\Sigma_kV_k^T$ 为矩阵A的截断奇异值分解
$A \approx U_k\Sigma_kV_k^T$
其中 $U_k$ 是 $m*k$ 矩阵， $V_k$ 是n*k矩阵， $\Sigma_k$ 是k阶对角矩阵；矩阵 $U_K$ 由完全奇异分解U的前k列，矩阵 $V_k$ 由V的前k列，矩阵 $\Sigma_k$ 由 $\Sigma$ 的前k个对角线元素得到。对角矩阵 $\Sigma_k$ 的秩比原始矩阵A的秩低。

(2)几何解释

从线性变换的角度理解奇异值分解， $m*n$ 矩阵A表示从n维空间 $R^n$ 到m空间 $R^m$ 的一个线性变换，
$T:x \to Ax$
x和Ax分别表示各自空间的向量。线性变换可以分解为三个简单的变换：一个坐标系的旋转或反射变换、一个坐标轴的缩放变换、另一个坐标系的旋转或反射。

对矩阵A进行奇异值分解，得到 $A=U\Sigma V^T$ ,V和U都是正交矩阵，所以V的列向量 $v_1,v_2,\dots,v_n$ 构成空间的一组标准正交基，表示 $R^n$ 中的正交坐标系的旋转或反射；U的列向量 $u_1,u_2,\dots,u_n$ 构成 $R^m$ 空间的一组标准正交基，表示 $R^m$ 中正交坐标系的旋转或反射； $\Sigma$ 的对角元素 $\sigma_1,\sigma_2,\dots,\sigma_n$ 是一组非负实数，表示 $R^n$ 中原始正坐标系坐标轴的 $\sigma_1,\sigma_2,\dots,\sigma_n$ 倍的缩放变换。

任意一个向量 $x \in R^n$ ，经过基于 $A=U\Sigma V^T$ 的线性变换，等价于经过坐标系的旋转或反射变换 $V^T$ ，坐标轴的缩放变换 $\Sigma$ ，以及坐标轴的旋转或反射变换U,得到相框 $Ax \in R^m$

二、奇异值分解的方法

（1）确定 $V$ 和 $\Sigma$

矩阵A是 $m*n$ 的正交实矩阵，则矩阵 $A^TA$ 是n阶实对称矩阵，因而 $A^TA$ 的特征值都是实数，并且存在一个n阶正实矩阵V实现 $A^TA$ 的对角化，使得 $V^T (A^TA)V = \Lambda$ 成立，其中 $\Lambda$ 是n阶对角矩阵，其对角元素由 $A^TA$ 的特征值组成。

而且， $A^TA$ 的特征值都是非负的。事实上，令 $\lambda$ 是 $A^TA$ 的一个特征值，x是对应的特征向量，则
$\|Ax\|^2 = x^TA^TAx=\lambda x^Tx =\lambda \|x\|^2$
于是
$\lambda = \frac{\|Ax\|^2}{\|x\|^2} \ge 0$
可以假设正交矩阵V的列排列使得对应的特征值形成降序排列。
$\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge 0$
计算特征值的平方根(实际上解释矩阵A的奇异值)
$\sigma_j = \sqrt{\lambda_j},j=1,2,\dots,n$
设矩阵A的秩是r,rank(A)=r,则矩阵 $A^TA$ 的秩也是r。由于 $A^TA$ 是对称矩阵，它的秩等于正的特征值的个数。

$\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_r \ge 0 ，\lambda_{r+1}=\lambda_{r+2}=\dots,\lambda_n=0$
对应的
$\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r \ge 0 ,\sigma_{r+1}=\sigma_{r+2}=\sigma_n=0$
令
$V_1 =[v_2,v_2,\dots,v_r],v_2=[v_{r+1},v_{r+2},\dots,v_n]$
其中 $v_2,\dots,v_r$ 为 $A^TA$ 的特征值对应的特征向量， $v_{r+1},\dots,v_n$ 为0特征值对应的特征向量。
则
$V=[V_1,V_2]$

这就是矩阵A的奇异值分解中的n阶正交矩阵V

令
$\Sigma_1 = \begin{bmatrix} \sigma_1 &\space &\space &\space \\[0.3em] \space & \sigma_2 & \space &\space\\[0.3em] \space&\space& \ddots \\[0.3em] \space & \space & \space &\sigma_r \end{bmatrix}$
则 $\Sigma_1$ 是个一个r阶对角矩阵，其对角线元素为按降序排列的正的 $\sigma_1,\dots,\sigma_r$ ，于是 $m*n$ 矩形对角矩阵 $\Sigma$ 可以表示为
$\Sigma = \begin{bmatrix} \Sigma_1 & 0 \\[0.3em] 0 & 0 \end{bmatrix}$
这就是矩阵A的奇异值分解中的 $m*n$ 矩阵对角矩阵 $\Sigma$

（2）确定U

接着构造m阶正交实矩阵U
令
$\begin{aligned} u_j = \frac{1}{\sigma_i}Av_j,j=1,2,\dots,r \\ U_1 = [u_1,u_2,\dots,u_r] \end{aligned}$
则有
$AV_1 = U_1\Sigma_1$
$U_1$ 的列向量构成正交基是因为
$\begin{aligned} u_i^T u_j =\bigg (\frac{1}{\sigma_i}v_i ^T A^T\bigg )\bigg(\frac{1}{\sigma_j}AV_j\bigg) \\ = \frac{1}{\sigma_i\sigma_j}v_i^T (A^T AV_j) \\ = \frac{\sigma_j}{\sigma_i}v_i^T v_j \\ =\delta_{ij},i=1,2\dots,r;j=1,2,\dots,r \end{aligned}$
对 $A^T$ 的非零空间的一组标准正交基 $\{u_{r+1},u_{r+2},\dots,u_m\}$ ，令
$U_2 = [u_{r+1},u_{r+2},\dots,u_m]$
并令
$U=[U_1,U_2]$

(3)得到奇异值分解

$A=U\Sigma V^T$

(4)证明 $U\Sigma V^T=A$

$\begin{aligned} U\Sigma V^T = [U_1,U_2] \begin{bmatrix} \Sigma_1 & 0 \\[0.3em] 0 & 0 \end{bmatrix} \begin{bmatrix} V_1^T \\[0.3em] V_2^T \end{bmatrix} \end{aligned} \\ =U_1\Sigma_1V_1^T \\ =AV_1V_1^T$

奇异值分解(SVD)

奇异值分解(SVD)

一、奇异值分解的定义与性质

(1)紧奇异值分解与截断奇异值分解

(a)紧奇异值分解

(b)截断奇异值分解

(2)几何解释

二、奇异值分解的方法

（1）确定和

（2）确定U

(3)得到奇异值分解

(4)证明

推荐阅读更多精彩内容

（1）确定 $V$ 和 $\Sigma$

(4)证明 $U\Sigma V^T=A$