线性代数笔记28--奇异值分解(SVD)

1. 奇异值分解

假设矩阵$A$有$m$行$n$列

奇异值分解就是在$A$的行向量上选取若干对标准正交基，对它作$A$矩阵变化并投射到了$A$的列空间上的正交基的若干倍数。

$$\begin{gathered} A\overrightarrow{v}=\overrightarrow{u}\sigma \\ \overrightarrow{u}\in R^m\overrightarrow{v}\in R^n \end{gathered}$$

其中$\sigma$被称为奇异值，我们在计算时将奇异值从大到小进行排列。

假设有$r$对行空间和列空间上的标准正交基可以进行上面的变化

那么我们得到了
$$\begin{gathered} A[\overrightarrow{v_1}\cdots \overrightarrow{v_r}\overrightarrow{v_{r+1}}\cdots \overrightarrow{v_n}]= \\ [\overrightarrow{u_1}\cdots \overrightarrow{u_r}\overrightarrow{u_{r+1}}\cdots \overrightarrow{u_m}]\left[\begin{array}{ccccc}{\sigma }_1& & & & \\ & {\sigma }_2& & & \\ & & \cdots & & \\ & & & {\sigma }_r& \\ & & & & \end{array}\right] \end{gathered}$$
其中
$\overrightarrow{u_1}\overrightarrow{u_2}\cdots \overrightarrow{u_r}\in C(A)$

$\overrightarrow{u_{r+1}}\cdots \overrightarrow{u_m}\in N(A^{\top })$

$\overrightarrow{v_1}\overrightarrow{v_2}\cdots \overrightarrow{v_r}\in C(A^{\top })$

$\overrightarrow{v_{r+1}}\cdots \overrightarrow{v_r}\in N(A)$

$\Sigma$矩阵有$m$行，$m-r$个零行。

SVD将四个空间联系起来， 将上面公式换成矩阵形式我们得到。

$$AV=U\Sigma$$
更进一步地有
$$A=U\Sigma V^{-1}=U\Sigma V^{\top }$$
加上行列号标识
$$A_{m\times n}=U_{m\times m}{\Sigma }_{m\times n}{V}_{n\times n}^{\top }$$

$A={\sigma }_1{u}_1{v}_1^{\top }+\cdots +{\sigma }_r{u}_r{v}_r^{\top }={\sum }_{i=1}^r{\sigma }_i{u}_i{v}_i^{\top }$

这也是svd最精华的地方，任何一个矩阵都可以写成至多$n$个

$m\times 1$矩阵和$1\times n$矩阵的倍数相加。

为了规范，我们约定${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r$。

如何求$A$的奇异值分解呢？

可以利用$A^{\top }AA{A}^{\top }$来求。

假设$A=U\Sigma V^{\top }$

$$\begin{gathered} A^{\top }A=V{\Sigma }^{\top }{U}^{\top }U\Sigma V^{\top }=V{\Sigma }^{\top }\Sigma V^{\top } \\ A{A}^{\top }=U{\Sigma }^{\top }{V}^{\top }V\Sigma U^{\top }=U{\Sigma }^{\top }\Sigma U^{\top } \end{gathered}$$
由于$A^{\top }AA{A}^{\top }$都是对称矩阵
$$\begin{gathered} (A{A}^{\top }{)}^{\top }=A{A}^{\top } \\ (A^{\top }A{)}^{\top }=A^{\top }A \end{gathered}$$
不严谨的说，它们可以分解为$S\Lambda S^{\top }$的形式。

因此求解$UV\Sigma$变为了求解$A{A}^{\top }{A}^{\top }A$的特征值和特征向量。

2. 举例子

上面的符号描述还是太抽象了，我们举例子。

2.1 案例1

$$A=\left[\begin{array}{cc}4& 4\\ -3& 3\end{array}\right]$$
$A$的转置
$$A^{\top }=\left[\begin{array}{cc}4& -3\\ 4& 3\end{array}\right]$$

$$A{A}^{\top }=\left[\begin{array}{cc}32& 0\\ 0& 18\end{array}\right]$$
$$\begin{gathered} {\lambda }_1=32 \\ {M}_1=A{A}^{\top }-{\lambda }_{1}I= \\ \left[\begin{array}{cc}0& 0\\ 0& -14\end{array}\right] \\ {M}_1\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right] \end{gathered}$$
因此$A{A}^{\top }$的一个特征向量为
$$\overrightarrow{u_1}=\left[\begin{array}{c}1\\ 0\end{array}\right]$$
同理
$$\begin{gathered} {\lambda }_2=18 \\ {M}_2=A{A}^{\top }-{\lambda }_{2}I= \\ \left[\begin{array}{cc}14& 0\\ 0& 0\end{array}\right] \\ {M}_2\left[\begin{array}{c}0\\ 1\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right] \end{gathered}$$
因此$A{A}^{\top }$的另一个特征向量为
$$\overrightarrow{u_2}=\left[\begin{array}{c}0\\ 1\end{array}\right]$$
因此我们可以得到矩阵$U$

$$U=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

另一方面
$$A^{\top }A=\left[\begin{array}{cc}25& 7\\ 7& 25\end{array}\right]$$
同理我们可以求得
$$\begin{gathered} (25-\lambda )(25-\lambda )-49=0 \\ (\lambda -32)(\lambda -18)=0 \\ {\lambda }_1=32{\lambda }_2=18 \end{gathered}$$
对应的
$$\begin{gathered} M_1^{\prime }=A^{\top }A-{\lambda }_{1}I=\left[\begin{array}{cc}-7& 7\\ 7& -7\end{array}\right] \\ {M}_1^{\prime }\left[\begin{array}{c}1\\ 1\end{array}\right]=0 \end{gathered}$$
因此$A^{\top }A$的一个特征向量单位化后
$$\overrightarrow{v_1}=\frac{\sqrt{2}}{2}\left[\begin{array}{c}1\\ 1\end{array}\right]$$
同理
$$\begin{gathered} M_2^{\prime }=A^{\top }A-{\lambda }_{2}I=\left[\begin{array}{cc}7& 7\\ 7& 7\end{array}\right] \\ {M}_2^{\prime }\left[\begin{array}{c}1\\ -1\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right] \end{gathered}$$
$A^{\top }A$的另一个特征向量单位化后
$$\overrightarrow{v_2}=\frac{\sqrt{2}}{2}\left[\begin{array}{c}1\\ -1\end{array}\right]$$
因此得到矩阵$V$

$$V=\left[\begin{array}{cc}\frac{\sqrt{2}}{2}& \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}& -\frac{\sqrt{2}}{2}\end{array}\right]$$

又有${\sigma }^2=\lambda$

那么$\Sigma$矩阵为

$$\Sigma =\left[\begin{array}{cc}4\sqrt{2}& 0\\ 0& 3\sqrt{2}\end{array}\right]$$

最终分解形式为
$$A=U\Sigma V^{\top }=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\left[\begin{array}{cc}4\sqrt{2}& 0\\ 0& 3\sqrt{2}\end{array}\right]\left[\begin{array}{cc}\frac{\sqrt{2}}{2}& \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}& -\frac{\sqrt{2}}{2}\end{array}\right]$$
我们验算后发现，右边符号不对劲；得到的矩阵为
$$\left[\begin{array}{cc}4& 4\\ 3& -3\end{array}\right]$$
因此上面有一步错误
验证
$$\begin{gathered} A\overrightarrow{v_1}=\left[\begin{array}{cc}4& 4\\ -3& 3\end{array}\right]\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}\end{array}\right]=\left[\begin{array}{c}4\sqrt{2}\\ 0\end{array}\right]={\sigma }_1\overrightarrow{v_1} \\ A\overrightarrow{v_2}=\left[\begin{array}{cc}4& 4\\ -3& 3\end{array}\right]\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2}\end{array}\right]=\left[\begin{array}{c}0\\ -3\sqrt{2}\end{array}\right]\ne {\sigma }_2\overrightarrow{v_2} \end{gathered}$$
因此$\overrightarrow{v_2}\ne \left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2}\end{array}\right]$，我们符号换下下就好了。

$$\overrightarrow{v_2}=\left[\begin{array}{c}-\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}\end{array}\right]$$

最终$A$的奇异值分解形式为

$$A=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\left[\begin{array}{cc}4\sqrt{2}& 0\\ 0& 3\sqrt{2}\end{array}\right]\left[\begin{array}{cc}\frac{\sqrt{2}}{2}& \frac{\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2}& \frac{\sqrt{2}}{2}\end{array}\right]$$
变成秩1矩阵相乘相加的形式为
$$A=4\sqrt{2}\left[\begin{array}{c}1\\ 0\end{array}\right]\left[\begin{array}{cc}\frac{\sqrt{2}}{2}& \frac{\sqrt{2}}{2}\end{array}\right]+3\sqrt{2}\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{cc}-\frac{\sqrt{2}}{2}& \frac{\sqrt{2}}{2}\end{array}\right]$$

2.2 案例2

过程就省略一些了
$$\begin{gathered} A=\left[\begin{array}{ccc}1& 0& -1\\ 0& 1& 0\end{array}\right] \\ {A}^{\top }=\left[\begin{array}{cc}1& 0\\ 0& 1\\ -1& 0\end{array}\right] \end{gathered}$$
$$\begin{gathered} A^{\top }A=\left[\begin{array}{ccc}1& 0& -1\\ 0& 1& 0\\ -1& 0& 1\end{array}\right] \\ {\lambda }_1=2,{\lambda }_1=1,{\lambda }_3=0 \\ {v}_1=\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ 0\\ -\frac{\sqrt{2}}{2}\end{array}\right]v_2=\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right]v_3=\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ 0\\ \frac{\sqrt{2}}{2}\end{array}\right] \end{gathered}$$
因此
$$V=\left[\begin{array}{ccc}\frac{\sqrt{2}}{2}& 0& \frac{\sqrt{2}}{2}\\ 0& 1& 0\\ -\frac{\sqrt{2}}{2}& 0& \frac{\sqrt{2}}{2}\end{array}\right]$$
同理
$$\begin{gathered} A{A}^{\top }=\left[\begin{array}{cc}2& 0\\ 0& 1\end{array}\right] \\ {\lambda }_1=2,{\lambda }_2=1 \\ {u}_1=\left[\begin{array}{c}1\\ 0\end{array}\right]u_2=\left[\begin{array}{c}0\\ 1\end{array}\right] \end{gathered}$$
因此
$$U=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$
最终$A$的奇异值分解为
$$\begin{gathered} A=U\Sigma V^{\top } \\ =\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\left[\begin{array}{ccc}\sqrt{2}& 0& 0\\ 0& 1& 0\end{array}\right]\left[\begin{array}{ccc}\frac{\sqrt{2}}{2}& 0& -\frac{\sqrt{2}}{2}\\ 0& 1& 0\\ \frac{\sqrt{2}}{2}& 0& \frac{\sqrt{2}}{2}\end{array}\right] \end{gathered}$$
变成秩1矩阵相乘相加的形式为
$$A=\sqrt{2}\left[\begin{array}{c}1\\ 0\end{array}\right]\left[\begin{array}{ccc}\frac{\sqrt{2}}{2}& 0& \frac{\sqrt{2}}{2}\end{array}\right]+1\left[\begin{array}{c}0\\ 1\end{array}\right]\left[\begin{array}{ccc}0& 1& 0\end{array}\right]$$

2.3 案例3

$$A=\left[\begin{array}{ccc}1& -2& 0\\ 0& -2& 1\end{array}\right]$$

$$\begin{gathered} A^{\top }=\left[\begin{array}{cc}1& 0\\ -2& -2\\ 0& 1\end{array}\right] \\ {A}^{\top }A=\left[\begin{array}{ccc}1& -2& 0\\ -2& 8& -2\\ 0& -2& 1\end{array}\right] \\ {\lambda }_1=9,{\lambda }_2=1,{\lambda }_3=0 \\ {v}_1=\left[\begin{array}{c}\frac{\sqrt{2}}{6}\\ -\frac{2\sqrt{2}}{3}\\ \frac{\sqrt{2}}{6}\end{array}\right]v_2=\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ 0\\ -\frac{\sqrt{2}}{2}\end{array}\right]v_3=\left[\begin{array}{c}\frac{2}{3}\\ \frac{1}{3}\\ \frac{2}{3}\end{array}\right] \end{gathered}$$
因此
$$V=\left[\begin{array}{ccc}\frac{\sqrt{2}}{6}& \frac{\sqrt{2}}{2}& \frac{2}{3}\\ -\frac{2\sqrt{2}}{3}& 0& \frac{1}{3}\\ \frac{\sqrt{2}}{6}& \frac{\sqrt{2}}{2}& \frac{2}{3}\end{array}\right]$$
同理
$$\begin{gathered} A{A}^{\top }=\left[\begin{array}{cc}5& 4\\ 4& 5\end{array}\right] \\ {\lambda }_1=9{\lambda }_2=1 \\ {u}_1=\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}\end{array}\right]u_2=\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2}\end{array}\right] \end{gathered}$$
因此
$$U=\left[\begin{array}{cc}\frac{\sqrt{2}}{2}& \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}& -\frac{\sqrt{2}}{2}\end{array}\right]$$
最终$A$的奇异值分解为
$$\begin{gathered} A=U\Sigma V^{\top }= \\ \left[\begin{array}{cc}\frac{\sqrt{2}}{2}& \frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}& -\frac{\sqrt{2}}{2}\end{array}\right]\left[\begin{array}{ccc}3& 0& 0\\ 0& 1& 0\end{array}\right]\left[\begin{array}{ccc}\frac{\sqrt{2}}{6}& -\frac{2\sqrt{2}}{3}& \frac{\sqrt{2}}{6}\\ \frac{\sqrt{2}}{2}& 0& -\frac{\sqrt{2}}{2}\\ \frac{2}{3}& \frac{1}{3}& \frac{2}{3}\end{array}\right] \end{gathered}$$
变成秩1矩阵相乘相加的形式为
$$\begin{gathered} A=3\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}\end{array}\right]\left[\begin{array}{ccc}\frac{\sqrt{2}}{6}& -\frac{2\sqrt{2}}{3}& \frac{\sqrt{2}}{6}\end{array}\right]+ \\ 1\left[\begin{array}{c}\frac{\sqrt{2}}{2}\\ -\frac{\sqrt{2}}{2}\end{array}\right]\left[\begin{array}{ccc}\frac{\sqrt{2}}{2}& 0& -\frac{\sqrt{2}}{2}\end{array}\right] \end{gathered}$$

参考

mit_svd
svd_numerical_examples
zhihu-svd