奇异值分解

作者: 单调不减 | 来源:发表于2019-06-19 15:32 被阅读0次

统计学习方法——修炼学习笔记15：奇异值分解
推荐系统（三）：基于矩阵分解的推荐算法
（转）奇异值分解（SVD）和主成分分析法（PCA）
转载《奇异值分解（SVD）》
singular value decomposition（奇异值
强大的矩阵奇异值分解(SVD)及其应用(转)
SVD和PCA
第30课奇异值分解
[转]奇异值分解SVD简介及其在推荐系统中的简单应用
转-奇异值分解

奇异值分解我写过一个简短的理解，记录于https://www.jianshu.com/p/8c7dac32620f，
这次又写一遍完全是因为《统计学习方法》的奇异值分解讲得太详细了，占了25页的篇幅，且大致翻看后面章节后发现奇异值分解的应用很多，因此决定对奇异值分解再重新学习一遍。

1、奇异值分解的定义与基本性质

任意一个 $m\times n$ 矩阵，都可以表示为三个矩阵的乘积（因子分解）形式：

$A=U\Sigma V^T$

其中 $U$ 是 $m$ 阶正交矩阵、 $\Sigma$ 是由降序排列的非负的对角线元素组成的 $m\times n$ 矩形对角阵、 $V$ 是 $n$ 阶正交矩阵。即这三个矩阵满足：

$UU^T=I$

$VV^T=I$

$\Sigma=diag(\sigma_1,\sigma_2,\dots,\sigma_p)$

$\sigma_1\geq \sigma_2\geq \dots \geq \sigma_p\geq 0$

$p=\min(m,n)$

$U\Sigma V^T$ 称为矩阵 $A$ 的奇异值分解（singular value decomposition，SVD）。

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

证明：

证明是构造性的，对给定矩阵，不妨设 $m\geq n$ 。

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

矩阵 $A$ 是 $m\times n$ 实矩阵，则 $A^T A$ 是 $n$ 阶实对称矩阵，因而 $A^T A$ 的特征值都是实数，且存在一 $n$ 阶正交实矩阵 $V$ 实现 $A^T A$ 的对角化，使得 $V^T (A^T A)V=\Lambda$ ，其中 $\Lambda$ 是 $n$ 阶对角矩阵，其对角线元素由 $A^T A$ 的特征值组成，且 $A^T A$ 的特征值都是非负的。事实上，令 $\lambda$ 是 $A^T A$ 的一个特征值， $x$ 是对应的特征向量，则：

$||Ax||^2=x^T A^T Ax=\lambda x^T x=\lambda ||x||^2$

于是：

$\lambda=\frac{||Ax||^2}{||x||^2}\geq 0$

假设正交矩阵 $V$ 的列的排列使得对应特征值形成降序排列：

$\lambda_1\geq \lambda_2\geq \dots\geq \lambda_n\geq 0$

计算特征值平方根（实际就是矩阵 $A$ 的奇异值）：

$\sigma_i=\sqrt{\lambda_i},\quad i=1,2,\dots,n$

设矩阵 $A$ 的秩为 $r$ ，则矩阵 $A^T A$ 的秩也为 $r$ （通过证明 $Ax=0$ 和 $A^T Ax=0$ 同解即可证明）。由于 $A^T A$ 是对称矩阵，它的秩等于正的特征值的个数（因为 $A^T A$ 和与其相似的对角矩阵 $\Lambda$ 秩相等，而 $\Lambda$ 对角元素是 $A^T A$ 的特征值）。所以：

$\lambda_1\geq \lambda_2\geq \dots\geq \lambda_r\geq 0,\quad \lambda_{r+1}=\dots=\lambda_n=0$

从而：

$\sigma_1\geq \sigma_2\geq \dots\geq \sigma_r\geq 0,\quad \sigma_{r+1}=\dots=\sigma_n=0$

令：

$V_1=[v_1\quad v_2\quad \dots \quad v_r]\quad V_2=[v_{r+1}\quad v_{r+2}\quad \dots \quad v_n]$

其中 $V_1$ 为正特征值对应的特征向量组成的矩阵， $V_2$ 则为0特征值对应的特征向量组成的矩阵。从而 $V$ 可以写成：

$V=[V_1\quad V_2]$

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

令：

$\Sigma_1=\left\{ \begin{matrix} \sigma_1 & & &\\ & \sigma_2 & &\\ & & \dots & \\ & & & \sigma_r \end{matrix} \right\}$

于是 $m\times n$ 矩阵对角矩阵 $\Sigma$ 可以表示为：

$\Sigma=\left\{ \begin{matrix} \Sigma_1&0\\ 0&0 \end{matrix} \right\}$

这就是矩阵 $A$ 奇异值分解中的 $\Sigma$ 。

（2）确定 $U$

令：

$u_j=\frac{1}{\sigma_j}Av_j,\quad i=1,2,\dots,r$

$U_1=[u_1\quad u_2\quad \dots\quad u_r]$

则有：

$AV_1=U_1\Sigma_1$

$U_1$ 的列向量构成了一组标准正交基，因为：

$\begin{aligned} u_i^T u_j&=(\frac{1}{\sigma_i}v_i^T A^T)(\frac{1}{\sigma_j}Av_j)\\ &=\frac{1}{\sigma_i \sigma_j}v_i^T(A^T Av_j)\\ &=\frac{1}{\sigma_i \sigma_j}v_i^T(\sigma_j^2 v_j)\\ &=\frac{\sigma_j}{\sigma_i}v_i^T v_j\\ &=\delta_{ij},\quad i=1,2,\dots,r,\quad j=1,2,\dots,r \end{aligned}$

因为 $i\neq j$ 时， $v_i$ 和 $v_j$ 正交。故有：

$\begin{equation} \delta_{ij}=\left\{ \begin{array}{rcl} 1 & & {i=j}\\ 0 & & {i\neq j} \end{array} \right. \end{equation}$

所以 $U_1$ 的列向量构成了一组标准正交基。

若将 $A$ 看成从 $R^n$ 到 $R^m$ 的线性变换，则 $A$ 的列空间和 $A$ 的值域 $R(A)$ 相同。因此 $u_1,u_2,\dots,u_r$ 也是 $R(A)$ 的一组标准正交基。因为 $N(A^T)=R(A)^\perp$ （即 $A^T$ 的零空间和 $R(A)$ 的正交补相同），故 $N(A^T)$ 的维数为 $m-r$ 。

令 $\{u_{r+1},u_{r+2},\dots,u_m\}$ 为 $N(A^T)$ 的一组标准正交基，并令：

$U_2=[u_{r+1}\quad u_{r+2}\quad \dots \quad u_m]$

$U=[U_1\quad U_2]$

则 $u_1,u_2,\dots,u_m$ 构成了 $R^m$ 的一组标准正交基。因此 $U$ 就是 $A$ 的奇异值分解中的 $m$ 阶正交矩阵。

（3）证明 $A=U\Sigma V^T$

$\begin{aligned} U\Sigma V^T&=[U_1\quad U_2]\lgroup{ \begin{matrix} \Sigma_1&0\\ 0&0 \end{matrix} \rgroup}\lgroup{ \begin{matrix} V_1^T\\ V_2^T \end{matrix} \rgroup}\\ &=U_1\Sigma_1 V_1^T\\ &=AV_1V_1^T\\ &=A \end{aligned}$

至此证明了矩阵 $A$ 存在奇异值分解。

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

上述定理给出的奇异值分解 $A=U\Sigma V^T$ 称为矩阵的完全奇异值分解。实际常用的是奇异值分解的紧凑形式和截断形式。紧奇异值分解是与原始矩阵等秩的奇异值分解，截断奇异值分解是比原始矩阵低秩的奇异值分解。

紧奇异值分解定义：

设有 $m\times n$ 实矩阵 $A$ ，其秩为 $rank(A)=r\leq\min(m,n)$ ，则称 $U_r\Sigma_r V_r^T$ 为 $A$ 的紧奇异值分解：

$A=U_r\Sigma_r V_r^T$

$U_r$ 是 $m\times r$ 矩阵，由完全奇异值分解中 $U$ 的前 $r$ 列得到， $V_r$ 是 $n\times r$ 矩阵，由完全奇异值分解中 $V$ 的前 $r$ 列得到， $\Sigma_r$ 是 $r$ 阶对角矩阵，由完全奇异值分解中 $\Sigma$ 的前 $r$ 个对角线元素得到。

截断奇异值分解定义：

设有 $m\times n$ 实矩阵 $A$ ，其秩为 $rank(A)=r$ ，且 $0<k<r$ ，则称 $U_k\Sigma_k V_k^T$ 为 $A$ 的截断奇异值分解：

$A\approx U_k\Sigma_k V_k^T$

$U_k$ 是 $m\times k$ 矩阵，由完全奇异值分解中 $U$ 的前 $k$ 列得到， $V_k$ 是 $n\times k$ 矩阵，由完全奇异值分解中 $V$ 的前 $k$ 列得到， $\Sigma_k$ 是 $k$ 阶对角矩阵，由完全奇异值分解中 $\Sigma$ 的前 $k$ 个对角线元素得到。

注意，紧奇异值分解完全还原原矩阵，截断奇异值分解近似还原原矩阵。因此在对矩阵数据进行压缩时，紧奇异值分解对应无损压缩，截断奇异值分解对应有损压缩。

3、几何解释

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

$T:x\rightarrow Ax$

$x\in R^n$ ， $Ax\in R^m$ ， $x$ 和 $Ax$ 分别是各自空间的向量。线性变换可以分解为三个简单的变换：一个坐标系的旋转或反射变换、一个坐标轴的缩放变换、另一个坐标系的旋转或反射变换。这就是奇异值分解的几何解释。

上图来自《统计学习方法》。我们可以很直观地看到奇异值分解的几何意义。

4、奇异值分解的计算

其实奇异值分解的计算过程已经蕴含在奇异值分解基本定理中了，对给定 $m\times n$ 矩阵 $A$ ，计算过程如下：

（1）计算 $A^T A$ 的特征值 $\lambda_i$ 和对应的特征值向量。

（2）将特征向量单位化，得到单位特征向量 $v_1,v_2,\dots,v_n$ 构成 $n$ 阶正交矩阵 $V$ ：

$V=[v_1\quad v_2\quad\dots\quad v_n]$

（3）计算 $A$ 的奇异值：

$\sigma_i=\sqrt{\lambda_i}$

构造 $m\times n$ 矩阵 $\Sigma$ ，主对角线元素为奇异值，其余元素为 $0$ 。

（4）对 $A$ 前 $r$ 个正奇异值，令：

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

得到：

$U_1=[u_1\quad u_2\quad\dots\quad u_r]$

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

$U_2=[u_{r+1}\quad u_{r+2}\quad\dots\quad u_m]$

则：

$U=[U_1\quad U_2]$

5、奇异值分解于矩阵近似

这部分内容是我没有接触过的，我以前只知道SVD和PCA类似，都可以做降维（其实PCA是SVD的特殊情形），但并没有从矩阵近似和压缩的角度看待过SVD。这一部分内容证明了一个结论：奇异值分解是在平方损失意义下对矩阵的最优近似。

首先定义矩阵的平方损失函数（也称为弗罗贝尼乌斯范数）：

设矩阵 $A\in R^{m\times n}$ ， $A=[a_{ij}]_{m\times n}$ ，定义矩阵 $A$ 的平方损失函数为：

$||A||_F=(\sum_{i=1}^m\sum_{j=1}^n (a_{ij})^2)^{\frac{1}{2}}$

下面证明一个结论：

$||A||_F=(\sigma_1^2+\sigma_2^2+\dots+\sigma_n^2)^{\frac{1}{2}}$

证明：

一般地，若 $Q$ 是 $m$ 阶正交矩阵，则：

$||QA||_F=||A||_F$

这是因为：

$\begin{aligned}||QA||_F^2&=||(Qa_1,Qa_2,\dots,Qa_n)||_F^2\\ &=\sum_{i=1}^n||Qa_i||^2=\sum_{i=1}^n||a_i||^2=||A||_F^2 \end{aligned}$

同理，若 $P$ 是 $n$ 阶正交矩阵，则：

$||AP||_F=||A||_F$

因此：

$||A||_F=||U\Sigma V^T||_F=||\Sigma||_F$

即：

$||A||_F=(\sigma_1^2+\sigma_2^2+\dots+\sigma_n^2)^{\frac{1}{2}}$

有了上述结论，我们接下来证明奇异值分解是在平方损失意义下对矩阵的最优近似。

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

$||A-X||_F=\min_{S\in M}||A-S||_F$

称矩阵 $X$ 为矩阵 $A$ 在平方误差下的最优近似。

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

$||A-X||_F=\min_{S\in M}||A-S||_F$

则：

$||A-X||_F=(\sigma_{k+1}^2+\sigma_{k+2}^2+\dots+\sigma_n^2)^{\frac{1}{2}}$

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

$\Sigma^{'}=\left\{ \begin{matrix} \sigma_1 & & & & \\ & \sigma_2 & & & \\ & & \dots & & \\ & & & \sigma_k & \\ & & & & 0& \\ & & & & & \dots& \\ & & & & & & 0& \\ \end{matrix} \right\}$

则：

$||A-A^{'}||_F=(\sigma_{k+1}^2+\sigma_{k+2}^2+\dots+\sigma_n^2)^{\frac{1}{2}}=\min_{S\in M}||A-S||_F$

定理2的具体证明过程见《统计学习方法》。

统计学习方法——修炼学习笔记15：奇异值分解
一、奇异值分解的定义与性质 1、定义与定理奇异值分解注意：奇异值分解不要求矩阵A是方阵，事实上矩阵的奇异值分解...
推荐系统（三）：基于矩阵分解的推荐算法
一、矩阵分解原理 1.1、奇异值分解奇异值分解（Singular Value Decomposition，SVD...
（转）奇异值分解（SVD）和主成分分析法（PCA）
奇异值分解（Singular Value Decomposition） 1.奇异值分解是矩阵分解的一种方法 ...
转载《奇异值分解（SVD）》
转自奇异值分解(SVD)原理与在降维中的应用。奇异值分解（Singular Value Decompositio...
singular value decomposition（奇异值
singular value decomposition（奇异值分解）
强大的矩阵奇异值分解(SVD)及其应用(转)
强大的矩阵奇异值分解(SVD)及其应用
SVD和PCA
SVD是奇异值分解，当矩阵不是方阵的时候，则这个矩阵是奇异矩阵。我们可以通过奇异值分解来获得特征矩阵。因为有的时候...
第30课奇异值分解
奇异值分解：简称，是矩阵最终和最好的分解，分解的因子是正交矩阵，对角矩阵，正交矩阵，任意矩阵都有这种奇异值分解对...
[转]奇异值分解SVD简介及其在推荐系统中的简单应用
本文先从几何意义上对奇异值分解SVD进行简单介绍，然后分析了特征值分解与奇异值分解的区别与联系，最后用python...
转-奇异值分解
We Recommend a Singular Value Decomposition 我们推荐奇异值分解奇异值...