1. 线性代数导论(30)-奇异值分解(最新讲义)
  2. 第三十讲:奇异值分解

线性代数导论(30)-奇异值分解(最新讲义)

第三十讲:奇异值分解

本讲我们介绍将一个矩阵写为$A=U\varSigma V^T$,分解的因子分别为正交矩阵、对角矩阵、正交矩阵,与前面几讲的分解不同的是,这两个正交矩阵通常是不同的,而且这个式子可以对任意矩阵使用,不仅限于方阵、可对角化的方阵等。

  • 在正定一讲中(第二十八讲)我们知道一个正定矩阵可以分解为$A=Q\Lambda Q^T$的形式,由于$A$对称性其特征向量是正交的,且其$\Lambda$矩阵中的元素皆为正,这就是正定矩阵的奇异值分解。在这种特殊的分解中,我们只需要一个正交矩阵$Q$就可以使等式成立。

  • 在对角化一讲中(第二十二讲),我们知道可对角化的矩阵能够分解为$A=S\Lambda S^T$的形式,其中$S$的列向量由$A$的特征向量组成,但$S$并不是正交矩阵,所以这不是我们希望得到的奇异值分解。

我们现在要做的是,在$A$的列空间中找到一组特殊的正交基$v_1,v_2,\cdots,v_r$,这组基在$A$的作用下可以转换为$A$的行空间中的一组正交基$u_1,u_2,\cdots,u_r$

用矩阵语言描述为$A\Bigg[v_1\ v_2\ \cdots\ v_r\Bigg]=\Bigg[\sigma_1u_1\ \sigma_2u_2\ \cdots\ \sigma_ru_r\Bigg]=\Bigg[u_1\ u_2\ \cdots\ u_r\Bigg]\begin{bmatrix}\sigma_1&&&\\&\sigma_2&&\\&&\ddots&\\&&&\sigma_n\end{bmatrix}$,即$Av_1=\sigma_1u_1,\ Av_2=\sigma_2u_2,\cdots,Av_r=\sigma_ru_r$,这些$\sigma$是缩放因子,表示在转换过程中有拉伸或压缩。而$A$的左零空间和零空间将体现在$\sigma$的零值中。

另外,如果算上左零、零空间,我们同样可以对左零、零空间取标准正交基,然后写为$A\Bigg[v_1\ v_2\ \cdots\ v_r\ v_{r+1}\ \cdots\ v_m\Bigg]=\Bigg[u_1\ u_2\ \cdots\ u_r\ u_{r+1}\ \cdots \ u_n\Bigg]\left[\begin{array}{c c c|c}\sigma_1&&&\\&\ddots&&\\&&\sigma_r&\\\hline&&&\begin{bmatrix}0\end{bmatrix}\end{array}\right]$,此时$U$是$m\times m$正交矩阵,$\varSigma$$m\times n$对角矩阵,$V^T$是$n\times n$正交矩阵。

最终可以写为$AV=U\varSigma$,可以看出这十分类似对角化的公式,矩阵$A$被转化为对角矩阵$\varSigma$,我们也注意到$U,\ V$是两组不同的正交基。(在正定的情况下,$U,\ V$都变成了$Q$。)。进一步可以写作$A=U\varSigma V^{-1}$,因为$V$是标准正交矩阵所以可以写为$A=U\varSigma V^T$

计算一个例子,$A=\begin{bmatrix}4&4\\-3&3\end{bmatrix}$,我们需要找到:

  • 行空间$\mathbb{R}^2$的标准正交基$v_1,v_2$
  • 列空间$\mathbb{R}^2$的标准正交基$u_1,u_2$
  • $\sigma_1>0, \sigma_2>0$

$A=U\varSigma V^T$中有两个标准正交矩阵需要求解,我们希望一次只解一个,如何先将$U$消去来求$V$?

这个技巧会经常出现在长方形矩阵中:求$A^TA$,这是一个对称正定矩阵(至少是半正定矩阵),于是有$A^TA=V\varSigma^TU^TU\varSigma V^T$,由于$U$是标准正交矩阵,所以$U^TU=I$,而$\varSigma^T\varSigma$是对角线元素为$\sigma^2$的对角矩阵。

现在有$A^TA=V\begin{bmatrix}\sigma_1&&&\\&\sigma_2&&\\&&\ddots&\\&&&\sigma_n\end{bmatrix}V^T$,这个式子中$V$即是$A^TA$的特征向量矩阵而$\varSigma^2$是其特征值矩阵。

同理,我们只想求$U$时,用$AA^T$消掉$V$即可。

我们来计算$A^TA=\begin{bmatrix}4&-3\\4&3\end{bmatrix}\begin{bmatrix}4&4\\-3&3\end{bmatrix}=\begin{bmatrix}25&7\\7&25\end{bmatrix}$,对于简单的矩阵可以直接观察得到特征向量$A^TA\begin{bmatrix}1\\1\end{bmatrix}=32\begin{bmatrix}1\\1\end{bmatrix},\ A^TA\begin{bmatrix}1\\-1\end{bmatrix}=18\begin{bmatrix}1\\-1\end{bmatrix}$,化为单位向量有$\sigma_1=32,\ v_1=\begin{bmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{bmatrix},\ \sigma_2=18,\ v_2=\begin{bmatrix}\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}\end{bmatrix}$

到目前为止,我们得到$\begin{bmatrix}4&4\\-3&3\end{bmatrix}=\begin{bmatrix}u_?&u_?\\u_?&u_?\end{bmatrix}\begin{bmatrix}\sqrt{32}&0\\0&\sqrt{18}\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\end{bmatrix}$,接下来继续求解$U$。

$AA^T=U\varSigma V^TV\varSigma^TU^T=U\varSigma^2U^T$,求出$AA^T$的特征向量即可得到$U$,$\begin{bmatrix}4&4\\-3&3\end{bmatrix}\begin{bmatrix}4&-3\\4&3\end{bmatrix}=\begin{bmatrix}32&0\\0&18\end{bmatrix}$,观察得$AA^T\begin{bmatrix}1\\0\end{bmatrix}=32\begin{bmatrix}1\\0\end{bmatrix},\ AA^T\begin{bmatrix}0\\1\end{bmatrix}=18\begin{bmatrix}0\\1\end{bmatrix}$。但是我们不能直接使用这一组特征向量,因为式子$AV=U\varSigma$明确告诉我们,一旦$V$确定下来,$U$也必须取能够满足该式的向量,所以此处$Av_2=\begin{bmatrix}0\\-\sqrt{18}\end{bmatrix}=u_2\sigma_2=\begin{bmatrix}0\\-1\end{bmatrix}\sqrt{18}$,则$u_1=\begin{bmatrix}1\\0\end{bmatrix},\ u_2=\begin{bmatrix}0\\-1\end{bmatrix}$。(这个问题在本讲的官方笔记中有详细说明。)

补充:$AB$的特征值与$BA$的特征值相同,证明来自Are the eigenvalues of AB equal to the eigenvalues of BA? (Citation needed!)

$\lambda\neq 0$,$v$是$AB$在特征值取$\lambda$时的的特征向量,则有$Bv\neq 0$,并有$\lambda Bv=B(\lambda v)=B(ABv)=(BA)Bv$,所以$Bv$是$BA$在特征值取同一个$\lambda$时的特征向量。

再取$AB$的特征值$\lambda=0$,则$0=\det{AB}=\det{A}\det{B}=\det{BA}$,所以$\lambda=0$也是$BA$的特征值,得证。

最终,我们得到$\begin{bmatrix}4&4\\-3&3\end{bmatrix}=\begin{bmatrix}1&0\\0&-1\end{bmatrix}\begin{bmatrix}\sqrt{32}&0\\0&\sqrt{18}\end{bmatrix}\begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\end{bmatrix}$

再做一个例子,$A=\begin{bmatrix}4&3\\8&6\end{bmatrix}$,这是个秩一矩阵,有零空间。$A$的行空间为$\begin{bmatrix}4\\3\end{bmatrix}$的倍数,$A$的列空间为$\begin{bmatrix}4\\8\end{bmatrix}$的倍数。
标准化向量得$v_1=\begin{bmatrix}0.8\\0.6\end{bmatrix},\ u_1=\frac{1}{\sqrt{5}}\begin{bmatrix}1\\2\end{bmatrix}$
$A^TA=\begin{bmatrix}4&8\\3&6\end{bmatrix}\begin{bmatrix}4&3\\8&6\end{bmatrix}=\begin{bmatrix}80&60\\60&45\end{bmatrix}$,由于$A$是秩一矩阵,则$A^TA$也不满秩,所以必有特征值$0$,则另特征值一个由迹可知为$125$。 继续求零空间的特征向量,有$v_2=\begin{bmatrix}0.6\\-0,8\end{bmatrix},\ u_1=\frac{1}{\sqrt{5}}\begin{bmatrix}2\\-1\end{bmatrix}$

最终得到$\begin{bmatrix}4&3\\8&6\end{bmatrix}=\begin{bmatrix}1&\underline {2}\\2&\underline{-1}\end{bmatrix}\begin{bmatrix}\sqrt{125}&0\\0&\underline{0}\end{bmatrix}\begin{bmatrix}0.8&0.6\\\underline{0.6}&\underline{-0.8}\end{bmatrix}$,其中下划线部分都是与零空间相关的部分。

  • $v_1,\ \cdots,\ v_r$是行空间的标准正交基;
  • $u_1,\ \cdots,\ u_r$是列空间的标准正交基;
  • $v_{r+1},\ \cdots,\ v_n$是零空间的标准正交基;
  • $u_{r+1},\ \cdots,\ u_m$是左零空间的标准正交基。

通过将矩阵写为$Av_i=\sigma_iu_i$形式,将矩阵对角化,向量$u,\ v$之间没有耦合,$A$乘以每个$v$都能得到一个相应的$u$。


技术交流学习,请加QQ微信:631531977
目录