第三十讲：奇异值分解

本讲我们介绍将一个矩阵写为$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$。