【线性代数】1.8SVD分解的证明

0.准备

为了论述矩阵的奇异值与奇异值分解，需要下面的结论：
（1）设$A\in C_r^{m\times n}(r>0)$，则$A^{H}A$是Hermite矩阵，（如果矩阵$A$不包含复数，那么$A^H=A^T$）且其特征值均是非负实数；
（2）$rank\left(A^{H}A\right)=rank\left(A\right)$；
（3）设$A\in C^{m\times n}$，则$A=O$的充要条件是$A^{H}A=O$；

证明：
（1）设：$A^{T}Ax=\lambda x(x?=0)$，则$x^T{A}^{T}Ax=\lambda x^{T}x$，即$${\Vert Ax\Vert }^2=\lambda {\Vert x\Vert }^2,$$故$\lambda ?0$，同理$A^{T}A$的特征值也全是非负实数.
（2）证明方程组$A^{H}Ax=0(1)$与$Ax=0(2)$同解
???如果$\alpha$是(2)的解，则$A\alpha =0$，显然有$A^{T}Ax=0$，即$\alpha$是(1)的解，故(2)的解全是(1)的解.
???若$\alpha$是(1)的解，即$A^{T}A\alpha =0$，那么${\alpha }^T{A}^{T}A\alpha =0$，即${\left(A\alpha \right)}^T\left(A\alpha \right)=0$.从而${\Vert A\alpha \Vert }^2=0$，故$A\alpha =0$.所以$\alpha$必是(2)的解，即 (1)的解全是(2)的解.
???综上所述，方程组(1)与(2)同解，即$rank\left(A^{H}A\right)=rank\left(A\right)$.
（3）充分性：$A=O?A^{T}A=O$，成立.
???必要性：将$A$写成列向量形式，$A=({\alpha }_1,{\alpha }_2,{\alpha }_3,?,{\alpha }_n)$，则
???$A^{T}A=?\begin{array}{c}{\alpha }_1^T\\ {\alpha }_2^T\\ {\alpha }_3^T\\ ?\\ {\alpha }_n^T\end{array}?({\alpha }_1,{\alpha }_2,{\alpha }_3,?,{\alpha }_n)=O?{\alpha }_i^T{\alpha }_i=0?{\alpha }_i$为零向量，因此矩阵$A$为零矩阵.

1.奇异值

??设$A\in C_r^{m\times n}(r>0)$，$A^{H}A$的特征值为$${\lambda }_1?{\lambda }_2???{\lambda }_{r>}{\lambda }_{r+1}=?={\lambda }_n=0$$则称${\sigma }_i=\sqrt{{\lambda }_i}(i=1,2,?,n)$为$A$的奇异值；当$A$为零矩阵时，它的奇异值都是0.

2.SVD分解

设$A\in C_r^{m\times n}(r>0)$，则存在$m$阶正交矩阵$U$和$n$阶正交矩阵$V$，满足$$\mathbf{A}=\mathbf{U}?\begin{array}{cccc}{\sigma }_1& & & \\ & ?& & \\ & & {\sigma }_r& \\ & & & O\end{array}?{\mathbf{V}}^{\mathbf{T}}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^{\mathbf{T}}={\sigma }_1{u}_1{v}_1^T+?+{\sigma }_r{u}_r{v}_r^T$$
或$${\mathbf{U}}^{\mathbf{T}}\mathbf{A}\mathbf{V}=\left[\begin{array}{cc}\mathbf{\Sigma }& \mathbf{O}\\ \mathbf{O}& \mathbf{O}\end{array}\right]$$
其中$r=rank(A)$，$\mathbf{\Sigma }=diag({\sigma }_1,{\sigma }_1,?,{\sigma }_r)$，$\mathbf{U}=\left(u_1,?,u_r,u_{r+1},?,u_m\right)$，$\mathbf{V}=\left(v_1,?,v_r,v_{r+1},?,v_n\right)$。习惯上，称${\sigma }_1?{\sigma }_2???{\sigma }_r>0$为矩阵$A$的全部非零奇异值.这个分解为奇异值分解，简称SVD.
?
矩阵$A^{T}A$、$A{A}^T$的特征值$\lambda$与${\sigma }_i$的关系
$$A=U\Sigma V^T?AV=U\Sigma ，写成列向量$$
$$\mathrm{A}({\mathrm{v}}_1?{\mathrm{v}}_{\mathrm{r}}{\mathrm{v}}_{\mathrm{r}+1}?{\mathrm{v}}_{\mathrm{n}})=({\mathrm{u}}_1?{\mathrm{u}}_{\mathrm{r}}{\mathrm{u}}_{\mathrm{r}+1}?{\mathrm{u}}_{\mathrm{m}})?\begin{array}{cccc}{\sigma }_1& & & \\ & ?& & \\ & & {\sigma }_{\mathrm{r}}& \\ & & & \mathrm{O}\end{array}?$$
同理，
$${\mathrm{A}}^{\mathrm{T}}({\mathrm{u}}_1?{\mathrm{u}}_{\mathrm{r}}{\mathrm{u}}_{\mathrm{r}+1}?{\mathrm{u}}_{\mathrm{m}})=({\mathrm{v}}_1?{\mathrm{v}}_{\mathrm{r}}{\mathrm{v}}_{\mathrm{r}+1}?{\mathrm{v}}_{\mathrm{n}})?\begin{array}{cccc}{\sigma }_1& & & \\ & ?& & \\ & & {\sigma }_{\mathrm{r}}& \\ & & & \mathrm{O}\end{array}?$$
$$\{\begin{array}{l}A{v}_i={\sigma }_i{u}_i\\ A^T{u}_i={\sigma }_i{v}_i\end{array}(i=1,?,r),\{\begin{array}{l}A{v}_i=0(i=r+1,?,n)\\ A^T{u}_i=0(i=r+1,?,m)\end{array}$$
所以
$$\begin{gathered} A^{T}A{v}_i={\sigma }_i^2{v}_i?v_i是A^{T}A关于{\sigma }_i^2的特征向量 \\ A{A}^T{u}_i={\sigma }_i^2{u}_i?u_i是A{A}^T关于{\sigma }_i^2的特征向量 \end{gathered}$$

3.SVD分解的证明

??记Hermite矩阵$A^{H}A$的特征值为$${\lambda }_1?{\lambda }_2???{\lambda }_{r>}{\lambda }_{r+1}=?={\lambda }_n=0$$存在$m$阶正交矩阵$V$，使得
$${\mathbf{V}}^{\mathbf{H}}({\mathbf{A}}^{\mathbf{H}}\mathbf{A})\mathbf{V}=?\begin{array}{ccc}{\lambda }_1& & \\ & ?& \\ & & {\lambda }_n\end{array}?=\left[\begin{array}{cc}{\mathbf{\Sigma }}^2& \mathbf{O}\\ \mathbf{O}& \mathbf{O}\end{array}\right]$$
将$\mathbf{V}$分块为
$$\mathbf{V}=\left[{\mathbf{V}}_1?{\mathbf{V}}_2\right]，{\mathbf{V}}_1\in C_r^{n\times r}，{\mathbf{V}}_2\in C_{n?r}^{n\times (n?r)}$$
改写上述式子${\mathbf{V}}^{\mathbf{H}}({\mathbf{A}}^{\mathbf{H}}\mathbf{A})\mathbf{V}$为$${\mathbf{A}}^{\mathbf{H}}\mathbf{A}\mathbf{V}=\mathbf{V}\left[\begin{array}{cc}{\mathbf{\Sigma }}^2& \mathbf{O}\\ \mathbf{O}& \mathbf{O}\end{array}\right]$$
则有
$${\mathbf{A}}^{\mathbf{H}}\mathbf{A}{\mathbf{V}}_1=\mathbf{V}{\mathbf{\Sigma }}^2，{\mathbf{A}}^{\mathbf{H}}\mathbf{A}{\mathbf{V}}_2=\mathbf{O}$$由${\mathbf{A}}^{\mathbf{H}}\mathbf{A}{\mathbf{V}}_1=\mathbf{V}{\mathbf{\Sigma }}^2$可得，${\mathbf{V}}_1^{\mathrm{H}}{\mathbf{A}}^{\mathrm{H}}\mathbf{A}{\mathbf{V}}_1={\mathbf{\Sigma }}^2或者{({\mathbf{A}\mathbf{V}}_1{\mathbf{\Sigma }}^{?1})}^{\mathrm{H}}(\mathbf{A}{\mathbf{V}}_1{\mathbf{\Sigma }}^{?1})={\mathbf{I}}_{\mathrm{r}}$

由${\mathbf{A}}^{\mathbf{H}}\mathbf{A}{\mathbf{V}}_2=\mathbf{O}$可得，${(\mathbf{A}{\mathbf{V}}_2)}^H\left(\mathbf{A}{\mathbf{V}}_2\right)=\mathbf{O}或\mathbf{A}{\mathbf{V}}_2=\mathbf{O}$
??令${\mathbf{U}}_1=\mathbf{A}{\mathbf{V}}_1{\mathbf{\Sigma }}^{?1}$，则${\mathbf{U}}_1^{\mathbf{H}}{\mathbf{U}}_1={\mathbf{I}}_{\mathbf{r}}$，即$U_1$的$r$个列是两两正交的单位向量，记作${\mathbf{U}}_1=\left(u_1,u_2,?,u_r\right)$.将$u_1,?,u_r$扩充为$C^m$的标准正交基，记增添的向量为$u_{r+1},?,u_m$，并构造矩阵${\mathbf{U}}_2=\left(u_{r+1},?,u_m\right)$，则
$$\mathbf{U}=\left[{\mathbf{U}}_1?{\mathbf{U}}_2\right]=\left(u_1,u_2,?,u_r,u_{r+1},?,u_m\right)$$
是$m$阶正交矩阵，且有
$${\mathbf{U}}_1^H{\mathbf{U}}_1={\mathbf{I}}_r，{\mathbf{U}}_2^H{\mathbf{U}}_1=\mathbf{O}$$于是可得
$${\mathbf{U}}^H\mathbf{A}\mathbf{V}={\mathbf{U}}^H\left[\mathbf{A}{\mathbf{V}}_1?\mathbf{A}{\mathbf{V}}_2\right]=\left[\begin{array}{c}{\mathbf{U}}_1^H\\ {\mathbf{U}}_2^H\end{array}\right]\left[{\mathbf{U}}_1\mathbf{\Sigma }?\mathbf{O}\right]=\left[\begin{array}{cc}{\mathbf{U}}_1^H{\mathbf{U}}_1\mathbf{\Sigma }& O\\ {\mathbf{U}}_2^H{\mathbf{U}}_1\mathbf{\Sigma }& O\end{array}\right]=\left[\begin{array}{cc}\mathbf{\Sigma }& \mathbf{O}\\ \mathbf{O}& \mathbf{O}\end{array}\right]证毕$$
改写${\mathbf{U}}^{\mathbf{T}}\mathbf{A}\mathbf{V}=\left[\begin{array}{cc}\mathbf{\Sigma }& \mathbf{O}\\ \mathbf{O}& \mathbf{O}\end{array}\right]$为
$$\mathbf{A}=\mathbf{U}\left[\begin{array}{cc}\mathbf{\Sigma }& \mathbf{O}\\ \mathbf{O}& \mathbf{O}\end{array}\right]{\mathbf{V}}^H$$称上式为矩阵A的奇异值分解.

4.例题

求矩阵$A=?\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}?$的奇异值分解.
解：

方法1：

$A^{T}A=?\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 1& 1& 2\end{array}?$的特征值是${\lambda }_1=3，{\lambda }_2=1，{\lambda }_3=0$，对应的特征向量依次为
$${\xi }_1=?\begin{array}{c}1\\ 1\\ 2\end{array}?，{\xi }_2=?\begin{array}{c}1\\ ?1\\ 0\end{array}?，{\xi }_3=?\begin{array}{c}1\\ 1\\ ?1\end{array}?$$于是可得
$$rank(A)=2，\Sigma =\left[\begin{array}{cc}\sqrt{3}& 0\\ 0& 1\end{array}\right]$$存在矩阵$V$，使得矩阵$A^{T}A$可以相似对角化$$V^T(A^{T}A)V=diag({\lambda }_1,{\lambda }_2,{\lambda }_3)$$
即矩阵$V$由${\lambda }_1,{\lambda }_2,{\lambda }_3$对应的单位特征向量组成，所以$$V=\left[\begin{array}{ccc}\frac{{\xi }_1}{\Vert {\xi }_1\Vert }& \frac{{\xi }_2}{\Vert {\xi }_2\Vert }& \frac{{\xi }_3}{\Vert \xi 3\Vert }\end{array}\right]=?\begin{array}{ccc}\frac{1}{\sqrt{6}}& \frac{1}{\sqrt{2}}& \frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{6}}& ?\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{3}}\\ \frac{2}{\sqrt{6}}& 0& ?\frac{1}{\sqrt{3}}\end{array}?$$计算
$$U_1=A{V}_1{\Sigma }^{?1}=?\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& ?\frac{1}{\sqrt{2}}\\ 0& 0\end{array}?$$由于矩阵$U$是正交矩阵，向量两两正交，构造
$$U_2=?\begin{array}{c}0\\ 0\\ 1\end{array}?，U=\left[U_1?U_2\right]=?\begin{array}{ccc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}& 0\\ \frac{1}{\sqrt{2}}& ?\frac{1}{\sqrt{2}}& 0\\ 0& 0& 1\end{array}?$$则$A$的奇异值分解为
$$A=U?\begin{array}{ccc}\sqrt{3}& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}?V^T$$

方法2：

矩阵$A$可分解为$\mathbf{A}=\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^{\mathbf{T}}$，所以只需求出$\mathbf{U}\mathbf{\Sigma }{\mathbf{V}}^{\mathbf{T}}$
（1）分别求出矩阵${\mathbf{A}}^{\mathbf{T}}\mathbf{A}$、$\mathbf{A}{\mathbf{A}}^{\mathbf{T}}$的特征值及对应的特征向量；
（2）矩阵${\mathbf{A}}^{\mathbf{T}}\mathbf{A}$、$\mathbf{A}{\mathbf{A}}^{\mathbf{T}}$的特征值为对角矩阵$\mathbf{\Sigma }$的元素（其实两个矩阵特征值相同），${\mathbf{A}}^{\mathbf{T}}\mathbf{A}$、$\mathbf{A}{\mathbf{A}}^{\mathbf{T}}$的特征值对应单位的特征向量为矩阵$\mathbf{U}$、$\mathbf{V}$
（3）写SVD分解表达式

??
证明：矩阵${\mathbf{A}}^{\mathbf{T}}\mathbf{A}$($m$阶)与$\mathbf{A}{\mathbf{A}}^{\mathbf{T}}$($n$阶)的非零特征值集合相同.

证：$r(A{A}^T)=r(A^T)，r(A^{T}A)=r(A)=r，r(A)=r(A^T)$，故
#{ATA的非零特征值}=r=#{AAT的非零特征值}\#\{A^TA\mathrm{的非零特征值}\}=r=\#\{AA^T\mathrm{的非零特征值}\}#{ ATA的非零特征值}=r=#{ AAT的非零特征值}
设$\lambda$是$A^{T}A$的非零特征值，即$?x，使得A^{T}Ax=\lambda x$
则有$A{A}^{T}Ax=\lambda Ax(Ax?=0)$，故$\lambda$也是$A{A}^T$的非零特征值，反之亦然
因此，$A{A}^T$和$A^{T}A$具有相同非零特征值.

??

解：
方法1中，已经求出矩阵$\mathbf{\Sigma }$、$\mathbf{V}$。那么只需求出矩阵$\mathbf{U}$，矩阵$\mathbf{A}{\mathbf{A}}^{\mathbf{T}}$为
$A{A}^T=?\begin{array}{ccc}2& 1& 0\\ 1& 2& 0\\ 0& 0& 0\end{array}?$的特征值为${\lambda }_1=3，{\lambda }_2=1，{\lambda }_3=0$，对应的特征向量依次为
$${\xi }_1=?\begin{array}{c}1\\ 1\\ 0\end{array}?，{\xi }_2=?\begin{array}{c}1\\ ?1\\ 0\end{array}?，{\xi }_3=?\begin{array}{c}0\\ 0\\ 1\end{array}?$$
单位化后，得
$$U=?\begin{array}{ccc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}& 0\\ \frac{1}{\sqrt{2}}& ?\frac{1}{\sqrt{2}}& 0\\ 0& 0& 1\end{array}?$$
则$A$的奇异值分解为
$$A=U?\begin{array}{ccc}\sqrt{3}& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}?V^T$$