奇异值分解

奇异值分解我写过一个简短的理解，记录于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的具体证明过程见《统计学习方法》。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,874评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,102评论 3赞 391
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,676评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,911评论 1赞 290
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,937评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,935评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,860评论 3赞 416
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,660评论 0赞 271
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,113评论 1赞 308
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,363评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,506评论 1赞 346
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,238评论 5赞 341
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,861评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,486评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,674评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,513评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,426评论 2赞 352