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

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

首先来看定义

奇异值分解(Singular Value Decomposition)

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

$$A=U \left[ \begin{matrix} \sigma_1 && & \\ & \ddots && \\ &&\sigma_r& \\ &&&0 \end{matrix} \right] V^T=U\sum V^T$$

其中$\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\in R^{m\times n}，A^TA\in R^{n\times n}为半正定对称矩阵，从而A^TA的特征值非负$$

证明：

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

$$x^TA^TAx=(Ax)^T(Ax)=\sum_{i=1}^nx_i^{'2}\ge0\\ 其中Ax=(x^{'}_1,...,x^{'}_n)$$

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

引理2

$$对任意矩阵A\in R^{m\times n},\text{rank}(A)=\text{rank}(A^TA)$$

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

$$n-\text{rank}(A)=n-\text{rank}(A^TA)$$

从而可以证明该结论。接下来证明$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$同解，所以

$$n-\text{rank}(A)=n-\text{rank}(A^TA)\\ \text{rank}(A)=\text{rank}(A^TA)$$

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

证明

由于结论中有正交矩阵，而对称矩阵可以正交相似于对角阵，所以我们自然联想到构造对称矩阵。令$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$的特征值为

$$\sigma_1^2,\sigma_2^2,...,\sigma_r^2，其中\sigma_1\ge\sigma_2\ge...\ge\sigma_r>0，$$

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

$$A_2=\text{diag}\{\sigma_1^2,\sigma_2^2,...,\sigma_r^2,\underbrace{0,...,0}_{n-r个0}\}\in R^{n\times n}$$

如果记

$$S= \left[ \begin{matrix} \sigma_1 && \\ & \ddots & \\ &&\sigma_r \end{matrix} \right]\in R^{r\times r}$$

那么

$$A_2= \left[ \begin{matrix} S^2 &0 \\ 0 &0 \end{matrix} \right]$$

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

$$A_1=VA_2V^T\\ V^TA_1V=A_2$$

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

$$(V_1,V_2)^TA_1(V_1,V_2) =\left[ \begin{matrix} S^2 &0 \\ 0 &0 \end{matrix} \right]\\ V_1^TA_1 V_1=S^2, V_2^TA_1 V_1=0,V_1^TA_1 V_2=0,V_2^TA_1 V_2=0$$

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

$$V_1^TA^TA V_1=S^2\\ 先左乘S^{-1}，再右乘S^{-1}\\ S^{-1}V_1^TA^TA V_1S^{-1}=I_r\\ 因为S为对角矩阵，所以S^{-1}也为对角矩阵，从而(S^{-1})^T=S^{-1}，因此\\ S^{-1}V_1^TA^TA V_1S^{-1}=(S^{-1})^TV_1^TA^TA V_1S^{-1}=(A V_1S^{-1})^TA V_1S^{-1}=I_r\\ 记U_1=A V_1S^{-1}\in R^{m\times r},那么U_1^TU_1=0$$

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

首先由引理2可知

$$\text{rank}(U_1)=\text{rank}(U_1^TU_1)=\text{rank}(I_r)=r$$

接下来我们考虑$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_2=0,U_2^TU_2=I_{m-r}$$

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

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

$$V_2^TA^TA V_2=(A V_2)^TA V_2=0\\ AV_2=0\\ 这个推出关系在引理2中有说明$$

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

$$\begin{aligned} U^TAV&=(U_1,U_2)^TA(V_1,V_2)\\ &= \left[ \begin{matrix} U_1^TAV_1 & U_1^TAV_2 \\ U_2^TAV_1 & U_2^TAV_2 \\ \end{matrix} \right] \end{aligned}$$

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

$$\begin{aligned} U_1^TAV_1 &=(A V_1S^{-1})^TAV_1\\ &=S^{-1}V_1^TA^TAV_1\\ &=S^{-1}V_1^TA_1V_1\\ &=S^{-1}S^2\\ &=S \end{aligned}$$

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

$$U_1^TAV_2=0$$

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

$$U_2^TU_1=U_2^TA V_1S^{-1}=0\\ 因为S可逆，所以\\ U_2^TA V_1=0$$

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

$$U_2^TAV_2 =0$$

综上所述

$$\begin{aligned} U^TAV&=(U_1,U_2)^TA(V_1,V_2)\\ &= \left[ \begin{matrix} S & 0 \\ 0 & 0 \\ \end{matrix} \right]\\ &=\left[ \begin{matrix} \sigma_1 && & \\ & \ddots && \\ &&\sigma_r& \\ &&&0 \end{matrix} \right]\\ & {\overset{记录为}=}\sum \end{aligned}$$

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

$$A=U \left[ \begin{matrix} \sigma_1 && & \\ & \ddots && \\ &&\sigma_r& \\ &&&0 \end{matrix} \right] V^T=U\sum V^T$$

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

奇异值分解的证明二

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

$$A\in R^{m\times n},\text{rank } A=r,\\ A_1=A^TA\in R^{n\times n},\text{rank } A_1=r,\\ A_1正交相似于对角阵A_2, A_2=\text{diag}\{\sigma_1^2,\sigma_2^2,...,\sigma_r^2,\underbrace{0,...,0}_{n-r个0}\}\in R^{n\times n}\\ 其中\sigma_1\ge\sigma_2\ge...\ge\sigma_r>0$$

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

$$A^TAv_i =\begin{cases} \sigma_i^2v_i, & 1\le i\le r\\ 0, & r+1\le i\le k \end{cases}$$

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

$$v_i^TA^TAv_i=\sigma_i^2v_i^Tv_i=\sigma_i^2\\ ||Av_i||^2=\sigma_i^2\\ ||Av_i||=\sigma_i$$

记$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_i^Tu_i= \frac{v_i^TA^TAv_i}{\sigma_i^2}=\frac{\sigma_i^2}{\sigma_i^2}=1\\ u_i^Tu_j=\frac{v_i^TA^TAv_j}{\sigma_i\sigma_j}=\frac{\sigma_i^2v_i^Tv_j}{\sigma_i\sigma_j}\\ 因为v_i,v_j(i\ne j)正交，所以\\ u_i^Tu_j=\frac{\sigma_i^2v_i^Tv_j}{\sigma_i\sigma_j}=0$$

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

$$A(v_1,...,v_r)=(u_1,...,u_r)\text{diag}\{\sigma_1^2,\sigma_2^2,...,\sigma_r^2\}$$

这个形式已经和我们要证明的形式非常接近了，只要把剩余的向量添加上即可，先将$(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)$带入上式可得

$$A(v_1,...,v_n)=(u_1,...,u_m) \left[ \begin{matrix} \sigma_1 && & \\ & \ddots && \\ &&\sigma_r& \\ &&&0 \end{matrix} \right]$$

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

$$AV=U\left[ \begin{matrix} \sigma_1 && & \\ & \ddots && \\ &&\sigma_r& \\ &&&0 \end{matrix} \right]\\ A=U\left[ \begin{matrix} \sigma_1 && & \\ & \ddots && \\ &&\sigma_r& \\ &&&0 \end{matrix} \right]V^T=U\sum V^T$$

定理得证。

总结

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

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

参考资料:

矩阵奇异值分解

线性代数公开课