奇异值分解(1)——奇异值分解的证明

在学习机器学习的过程中经常碰到奇异值分解,之前对这个知识点不太熟悉,花了一点时间去学习了相关知识,准备写三篇博客,分别为奇异值分解的证明,奇异值分解的性质,奇异值分解的应用,这一篇是有关奇异值分解的证明,话不多说,进入正题。

首先来看定义

奇异值分解(Singular Value Decomposition)

设$A$是一个$m\times n$矩阵, 则存在$m$阶正交矩阵$U$和$n$阶正交矩阵$V$, 满足

其中$\text{r = rank A},\sum\in R^{m\times n}​$. 习惯上,设 $\sigma_1\ge\sigma_2\ge…\ge\sigma_r>0​$,称$\sigma_1,…,\sigma_r​$为奇异值(singular value). 称$U​$和$V​$的前$r​$列向量为奇异向量(singular vector). 这个分解为奇异值分解, 简称SVD.

这里要注意的一点是$\sum$右下角的$0$是$0$矩阵的意思,下面用两种方法给出这个定理的证明。

奇异值分解的证明一

在证明之前需要两个引理

引理1

证明:

$(A^TA)^T=A^TA$,所以$A^TA$为对称矩阵,接着证明$A^TA$为半正定对称矩阵。任取$x\in R^n$,考虑二次型

所以$A^TA$为半正定矩阵,所以$A^TA$的特征值非负。

引理2

如果我们可以证明$Ax=0,A^TAx=0​$同解,那么由解空间的维数公式可得

从而可以证明该结论。接下来证明$Ax=0,A^TAx=0$同解。

证明:

如果$Ax=0$,那么$A^TAx=A^T0=0$,所以$Ax=0$的解一定是$A^TAx=0$的解。

反之,如果$A^TAx=0$,两边左乘$x^T$可得$x^TA^TAx=x^T0=0$,所以$(Ax)^TAx=0$,从而$Ax=0$,所以$A^TAx=0$的解一定是$Ax=0$的解。

结合以上两点$Ax=0,A^TAx=0$同解,所以

以上两个引理会在证明中使用到,下面开始正式证明。

证明

由于结论中有正交矩阵,而对称矩阵可以正交相似于对角阵,所以我们自然联想到构造对称矩阵。令$A_1=A^TA\in R^{n\times n}$,设$\text{rank } A=r$,由引理2可得$\text {rank }A_1=\text {rank }(A^TA)=\text{rank } A=r$,而可对角化的矩阵的秩等于矩阵的非零特征值数量,对称矩阵显然可逆,所以$A_1$有$r$个非零特征值,由引理1我们知道$A_1$为半正定矩阵,其特征值均为非负数,所以$A_1$有$r$个正特征值,设$A_1$的特征值为

由对称矩阵的性质可知,$A_1$可以正交相似于对角矩阵

如果记

那么

我们$A_2​$设对应的正交矩阵为$V​$,从而

对$V$进行分块,记其前$r$列构成的矩阵为$V_1$,后$n-r$列构成的矩阵为$V_2$,$V=(V_1,V_2)$,带入计算可得

将$A_1=A^TA$带入第$1,4$个等式,分别对其处理,先处理第$1$个等式

所以$U_1$是$R^m$中正交向量组成的矩阵,我们可以将其补充成一个$R^{m\times m}$的正交矩阵,下面严格证明一下。

首先由引理2可知

接下来我们考虑$U_1^Tx=0$的解空间,由于$\text{rank}(U_1)=r,U_1^T\in R^{r\times m}$,所以$U_1^Tx=0$有$m-r$个线性无关的解$u_1,…,u_{m-r}$,对这些解利用施密特正交化,并对其单位化,可以得到$U_2=(u_1^,…,u_{m-r}^)$满足以下条件

结合$U_1^TU_1=I_r$,那么$U=(U_1,U_2)$为正交矩阵。

再来看处理第$4$个等式,将$A_1=A^TA$带入可得

现在我们找到了$U,V​$,就可以来计算$U^TAV​$,将其写成分块矩阵的形式。

分别分析这四个部分,先看$ U_1^TAV_1​$,将$U_1=A V_1S^{-1}, V_1^TA_1 V_1=S^2,A_1=A^TA​$带入

再看$U_1^TAV_2$,将$AV_2=0$带入可得

接着看$U_2^TAV_1 $,考虑$U_1=A V_1S^{-1},U_2^TU_1=0$

最后考虑$U_2^TAV_2 $,将$AV_2=0$带入可得

综上所述

注意$U,V​$为正交矩阵,所以上式也等价于

这就是奇异值分解的形式,证毕。

奇异值分解的证明二

前一部分和证明一相同,这里简单叙述下

设$(v_1,…,v_n),v_i\in R^n$为$A_1=A^TA$的单位特征正交向量,那么

注意对于$1\le i\le r$,

记$u_i = \frac{Av_i}{\sigma_i},u_i\in R^m,1\le i\le r$,我们来证明$(u_1,…,u_r)$为一组单位正交向量,注意$A^TAv_i =\sigma_i^2v_i,$

从而$(u_1,…,u_r)$为单位正交向量。现在将$u_i = \frac{Av_i}{\sigma_i}$变形为$Av_i =\sigma_i u_i,1\le i\le r$,将这$r$个式子写成矩阵的形式

这个形式已经和我们要证明的形式非常接近了,只要把剩余的向量添加上即可,先将$(u_1,…,u_r)$补充为正交基。

由于$v_i\in R^m$,所以由基扩张定理,可以将$(u_1,…,u_r)$扩张为$(u_1,…,u_r,u_{r+1},…u_m)$,使得$(u_1,…,u_r,u_{r+1},…u_m)$为$ R^m$的一组单位正交基。现在将$(v_1,…,v_n),(u_1,…,u_m)$带入上式可得

记$V=(v_1,…,v_n),U=(u_1,…,u_m)$,注意$U,V$均为正交矩阵,那么上式可以表达为

定理得证。

总结

回顾一下证明思路,证明一首先是从$A$构造对称矩阵$A^TA$,利用对称矩阵的正交相似性找到$V$,接着利用分块矩阵的形式找到$U$的一部分$U_1$,将其补充为$U$,最后利用之前的一些得到的一些性质证明了奇异值分解;证明二是证明一的简化版,主要利用了$ \frac{Av_i}{\sigma_i}$的正交性,本质上和证明一是相似的。

这部分的内容是比较理论的,但个人认为还是挺有必要的,后续还会介绍奇异值分解的性质以及应用。

参考资料:

矩阵奇异值分解

线性代数公开课