奇异值分解（singular value decomposition，SVD）是一种矩阵因子分解方法，是线性代数的概念，但在统计学习中被广泛使用，成为其重要工具。

任意一个$m \times n$矩阵，都可以表示为三个矩阵的乘积（因子分解）形式，分别是$m$阶正交矩阵、由降序排列的非负的对角线元素组成的$m \times n$矩形对角矩阵和$n$阶正交矩阵，称为该矩阵的奇异值分解。

矩阵的奇异值分解一定存在，但不唯一。

奇异值分解可以看作是矩阵数据压缩的一种方法，即用因子分解的方式近似地表示原始矩阵，这种近似是在平方损失意义下的最优近似。

15.1 奇异值分解的定义与性质

15.1.1 定义与定理

定义15.1（奇异值分解） 矩阵的奇异值分解是指，将一个非零的$m \times n$实矩阵$A, A \in R^{m \times n}$，表示为一下三个实矩阵乘积形式的运算，即进行矩阵的因子分解：

$A = U \Sigma V^T \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.1)$

其中$U$是$m$阶正交矩阵（orthogonal matrix），$V$是$n$阶正交矩阵，$\Sigma$是由降序排列的非负的对角线元素组成的$m \times n$矩形对角矩阵（rectangular diagonal matrix），满足

$UU^T = I$ $VV^T = I$ $\Sigma = diag(\sigma_1,\sigma_2,...,\sigma_p)$ $\sigma_1 \geq \sigma_2 \geq... \geq \sigma_p \geq 0$ $p = \min(m,n)$

$U \Sigma V^T$称为矩阵$A$的奇异值分解（singular value decomposition，SVD），$\sigma_i$称为矩阵$A$的奇异值（singular value），$U$的列向量称为左奇异向量（left singular value），$V$的列向量称为右奇异向量（right singular value）。

定理 15.1（奇异值分解基本定理） 若$A$为一$m \times n$实矩阵，$A \in R^{m\times n}$，则$A$的奇异值分解存在

$A = U \Sigma V^T \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.2)$

其中$U$是$m$阶正交矩阵，$V$是$n$阶正交矩阵，$\Sigma$是$m \times n$矩形对角矩阵，其对角线元素非负且按降序排列。

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

定理15.1给出的奇异值分解

$A = U \Sigma V^T$

又称为矩阵的完全奇异值分解（full singular value decomposition）。实际常用的是奇异值分解的紧凑形式和截断形式。紧奇异值分解是与原始矩阵等秩的奇异值分解，截断奇异值分解是比原始矩阵低秩的奇异值分解。

紧奇异值分解

定义 15.2 设有$m \times n$实矩阵$A$，其秩为$rank(A) = r,r \leq min(m,n)$，则称$U_r\Sigma_r V_r^T$为$A$的紧奇异值分解（compact singular value decomposition），即
$A =U_r\Sigma_r V_r^T \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.18)$
其中$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<r$，$r$为矩阵的秩）对应的部分，就得到矩阵的截断奇异值分解。实际应用中提到矩阵的奇异值分解时，通常指截断奇异值分解。

定义 15.3 设$A$为$m \times n$实矩阵，其秩$rank(A) = r$，且$ 0 < k < r$，则称$U_k\Sigma_k V_k^T$为矩阵$A$的截断奇异值分解（truncated singular value decomposition）

$A \approx U_k\Sigma_k V_k^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.19)$

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

在实际应用中，常常需要对矩阵的数据进行压缩，将其近似表示，奇异值分解提供了一种方法。紧奇异值分解对应着无损压缩，截断奇异值分解对应着有损压缩。

15.1.3 几何解释

从线性变换的角度理解奇异值分解，$m \times n$矩阵$A$表示从$n$维空间$R^n$到$m$维空间$R^m$的一个线性变换，

$T : x \rightarrow Ax$

$x \in R^n,Ax \in R^m$，$x$和$Ax$分别是各自空间的向量。

线性变换可以分解为三个简单的变换：

一个坐标系的旋转或反射变换；
一个坐标轴的缩放变换；
另一个坐标系的旋转或反射变换。

15.1.4 主要性质

（1）设矩阵$A$的奇异值分解为$A = U \Sigma V^T$，则以下关系成立：

$A^TA = (U \Sigma V^T)^T(U \Sigma V^T) = V(\Sigma^T \Sigma)V^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.20)$ $AA^T =(U \Sigma V^T)(U \Sigma V^T)^T = U(\Sigma \Sigma^T)U^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.21)$

也就是说，矩阵$A^TA$和矩阵$AA^T$的特征分解存在，且可以由矩阵$A$的奇异值分解的矩阵表示。$V$的列向量是$A^TA$的特征向量，$U$的列向量是$AA^T$的特征向量，$\Sigma$的奇异值是$A^TA$和$AA^T$的特征值的平方根。

（2）在矩阵$A$的奇异值分解中，奇异值、左奇异向量和右奇异向量之间存在对应关系。

由$A = U \Sigma V^T$易知

$AV = U\Sigma$

比较这一等式两端的第$j$列，得到

$Av_j = \sigma_j u_j\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.22)$

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

类似地，得到

$A^T u_j = \sigma_jv_j, \ \ \ j = 1,2,...,n\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.23)$ $A^Tu_j = 0,\ \ \ j = n+1,n+2,...,m$

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

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

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

（5）

矩阵$A$的$r$个右奇异向量$v_1,v_2,…,v_r$构成$A^T$的值域$R(A^T)$的一组标准正交基。
矩阵$A$的$n-r$个右奇异向量$v_{r+1},v_{r+2},…,v_n$构成$A$的零空间$N(A)$的一组标准正交基。
矩阵$A$的$r$个左奇异向量$u_1,u_2,…,u_r$构成值域$R(A)$的一组标准正交基。
矩阵$A$的$m-r$个左奇异向量$u_{r+1},u_{r+2},…,u_m$构成$A^T$的零空间$N(A^T)$的一组标准正交基。

15.2 奇异值分解的计算

矩阵$A$的奇异值分解可以通过求对称矩阵$A^TA$的特征值和特征向量得到。$A^TA$的特征向量构成正交矩阵$V$的列；$A^TA$的特征值$\lambda_j$的平方根为奇异值$\sigma_j$，即

$\sigma_j = \sqrt{\lambda_j} \ \ \ j = 1,2,...,n$

对其由大到小排列作为对角线元素，构成对角矩阵$\Sigma$；求正奇异值对应的左奇异向量，再求扩充的$A^T$的标准正交基，构成正交矩阵$U$的列。从而得到$A$的奇异值分解$A = U \Sigma V^T$。

（1）首先求$A^TA$的特征值和特征向量。

计算对称矩阵$W = A^TA$。

求解特征方程

$(W-\lambda I)x = 0$

得到特征值$\lambda_i$，并将特征值由大到小排列

$\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n \geq 0$

将特征值$\lambda_i(i= 1,2,…,n)$代入特征方程求得对应的特征向量。

（2）求$n$阶正交矩阵$V$

将特征向量单位化，得到单位特征向量$v_1,v_2,…,v_n$，构成$n$阶正交矩阵$V$；

$V = [v_1,v_2...v_n]$

（3）求$m \times n$对角矩阵$\Sigma$

计算$A$的奇异值

$\sigma_j = \sqrt{\lambda_j} \ \ \ j = 1,2,...,n$

构造$m \times n$矩形对角矩阵$\Sigma$，主对角元素是奇异值，其余元素是零，

$\Sigma = diag(\sigma_1,\sigma_2,...,\sigma_n)$

（4）求$m$阶正交矩阵$U$

对$A$的前$r$个正奇异值，令

$u_j = \frac{1}{\sigma_j}Av_j, \ \ \ j = 1,2,...,r$

得到

$U_1 = [u_1,u_2,...,u_r]$

求$A^T$的零空间的一组标准正交基$u_{r+1},r_{r+2},…,u_m$，令

$U_2 = [u_{r+1},r_{r+2},...,u_m]$

并令

$U = [U_1,U_2]$

（5）得到奇异值分解

$A = U \Sigma V^T$

实际应用的奇异值分解算法是通过求$A^TA$的特征值进行，但不直接计算$A^TA$。

15.3 奇异值分解与矩阵近似

15.3.1 弗罗贝尼乌斯范数

奇异值分解也是一种矩阵近似的方法，这个近似是在弗罗贝尼乌斯范数（Frobenius norm）意义下的近似。矩阵的弗罗贝尼乌斯范数是向量的$L_2$范数的直接推广，对应着机器学习中的平方损失函数。

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

$||A||_{F} = (\sum\limits_{i = 1}^{m} \sum\limits_{j = 1}^{n} ( a_{ij})^2 )^{ \frac{1}{2} }\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.25)$

引理 15.1 设矩阵$A \in R^{m \times n}$，$A$的奇异值分解为$U \Sigma V^T$，其中$\Sigma = diag(\sigma_1,\sigma_2,…,\sigma_n)$，则

$||A||_{F} = (\sigma_1^2,\sigma_2^2,...,\sigma_n^2)^{\frac{1}{2} }\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.26)$

15.3.2 矩阵的最优近似

奇异值分解是在平方损失（弗罗贝尼乌斯范数）意义下对矩阵的最优近似，即数据压缩。

定理 15.2 设矩阵$A \in R^{m \times n}$，矩阵的秩$rank(A) = r$，并设$\mathcal{M}$为$R^{m \times n}$中所有秩不超过$k$的矩阵集合，$ 0 < k <r$，则存在一个秩为$k$的矩阵$X \in \mathcal{M}$，使得

$||A - X||_{F} = \min\limits_{ S \in \mathcal{M} } ||A -S||_{F} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.31)$

称矩阵$X$为矩阵$A$在弗罗贝尼乌斯范数意义下的最优近似。

定理 15.3 设矩阵$A \in R^{m \times n}$，矩阵的秩$rank(A) = r$，有奇异值分解$A = U \Sigma V^T$，并设$\mathcal{M}$为$R^{m\times n}$中所有秩不超过$k$的矩阵的集合，$0<k<r$，若秩为$k$的矩阵$X \in \mathcal{M}$满足

$||A - X||_{F} = \min\limits_{S \in \mathcal{M} }||A -S||_{F}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.32)$

则

$||A - X||_{F} =( \sigma_{k+1}^2, \sigma_{k+2}^2,..., \sigma_n^2)^{ \frac{1}{2} }\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.33)$

特别地，若$A^{‘} = U \Sigma^{‘} V^T$，其中

$\left[ \begin{matrix} \sigma_1 & & & & & \\ & ...& & & 0 & \\ & & &\sigma_k & & \\ & & & 0 & & \\ & 0 & & & ...& \\ & & & & & 0 \\ \end{matrix} \right] = \left[ \begin{matrix} \Sigma_k &0 \\ 0&0 \end{matrix} \right]$

则

$||A-A^{'}||_F =(\sigma_{k+1}^2,\sigma_{k+2}^2,...,\sigma_n^2)^{\frac{1}{2}} =\min\limits_{S \in \mathcal{M}}||A -S||_F\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.34)$

定理 15.3 表明，在秩不超过$k$的$m\times n$矩阵的集合中，存在矩阵$A$的弗罗贝尼乌斯范数意义下的最优近似矩阵$X$。$A^{‘} = U \Sigma^{‘} V^T$是达到最优值的一个矩阵。

15.3.3 矩阵的外积展开式

矩阵$A$的奇异值分解$U\Sigma V^T$也可以由外积形式表示。事实上，若将$A$的奇异值分解看成矩阵$U\Sigma$和$V^T$的乘积，将$U\Sigma$按列向量分块，将$V^T$按行向量分块，即得

$U\Sigma = [\sigma_1u_1 \ \ \sigma_1u_1 \ \ ... \ \ \ \sigma_1u_1]$ $V^T =\left[ \begin{matrix} v_1^T\\ v_2^T\\ ...\\ v_N^T \end{matrix} \right]$

则

$A = \sigma_1u_1v_1^T + \sigma_2u_2v_2^T+...+\sigma_nu_nv_n^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.45)$

式$(15.45)$称为矩阵$A$的外积展开式，其中$u_kv_k^T$为$m\times n$矩阵，是列向量$u_k$和行向量$v_k^T$的外积，其第$i$行第$j$列元素为$u_k$的第$i$个元素与$v_k^T$的第$j$个元素的乘积。

$A$的外积展开式也可以写成下面的形式

$A = \sum\limits_{k=1}^nA_k = \sum\limits_{k=1}^n \sigma_ku_kv_k^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.46)$

其中$A_k = \sigma_ku_kv_k^T$是$m \times n$矩阵。式$(15.46)$将矩阵$A$分解为矩阵的有序加权和。

由矩阵$A$的外积展开式知，若$A$的秩为$n$，则

$A =\sigma_1u_1v_1^T + \sigma_2u_2v_2^T+...+\sigma_nu_nv_n^T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (15.47)$

一般地，设矩阵

$A_k =\sigma_1u_1v_1^T + \sigma_2u_2v_2^T+...+\sigma_ku_kv_k^T$

则$A_k$的秩为$k$，并且$A_k$是秩为$k$的矩阵中在弗罗贝尼乌斯范数意义下$A$的最优近似矩阵。矩阵$A_k$就是$A$的截断奇异值分解。

由于通常奇异值$\sigma_i$递减很快，所以$k$取很小值时，$A_k$也可以对$A$有很好的近似。

Blog

第十五章奇异值分解