奇异值分解
特征值分解是一个提取矩阵特征很不错的方法，但是它只是对方阵而言的，在现实的世界中，们看到的大部分矩阵都不是方阵。
奇异值分解基本定理：若 $ A$ 为 $ m \times n$ 实矩阵, 则 $ A$ 的奇异值分解存在
$A=U \Sigma V^$
$A=U \Sigma V^{T}=\left[\begin{array}{lll}\boldsymbol{u}{1} \& \cdots \& \boldsymbol{u}{m} \\\& \&\end{array}\right]\left[\begin{array}{ccc}\sigma{1} \& \& \& \\\& \ddots \& \& 0 \\\& \& \sigma{r} \\\& 0 \& \&0\end{array}\right]{m \times n}\left[\begin{array}{c}\boldsymbol{v}{1}^{T} \\\vdots \\\boldsymbol{v}_{n}^{T}\end{array}\right]$
$\Sigma$ 是 $m \times n$ 矩形对角矩阵，其对角线元素非负(半正定)，且按降序排列。可以发现， $ A$ 和 $\Sigma$ 是同型矩阵。
下面看看怎么得到矩阵 $U, \Sigma, V$ 。
$\begin{array}{l}A A^{T}=U \Sigma V^{T} V \Sigma^{T} U^{T}=U \Sigma \Sigma^{T} U^{T} \\A^{T} A=V \Sigma^{T} U^{T} U \Sigma V^{T}=V \Sigma^{T} \Sigma V^{T}\end{array}$
其中, $A A^{T}$ 是 $m$ 阶实对称矩阵, $A^{T} A$ 是 $n$ 阶实对称矩阵, $\Sigma \Sigma^{T}$ 是 $m$ 阶方阵, $\Sigma^{T} \Sigma$ 是 $n$ 阶方阵。
1) $A^ A$ 的特征值均为非负。令 $\lambda$ 是 $A^ A$ 的一个特征值, $\alpha$ 是对应的特征向量, 则
$\begin{array}{c}A^{T} A \alpha=\lambda \alpha \\\Rightarrow\\|A \alpha\\|^{2}=(A \alpha)^{T}(A \alpha)=\alpha^{T} A^{T} A \alpha=\alpha^{T} \lambda \alpha=\lambda\\|\alpha\\|^{2} \\\Rightarrow \lambda \geq 0\end{array}$
2）$A^ A$ 和 $ A A^ $ 拥有相同的非零特征值，并且保持相同重数，并且属于非零特征值的特征向量间存在制约关系。
a. 首先证明方程 $A x=0$ 和 $A^ A x=0$ 同解。
如果 $ A x=0$ , 则 $ A^(A x)=0$ , 所以 $ A x=0$ 的解为 $ A^ A x=0$ 的解。
对于 $ A^{T} A x=0$ , 两边同时乘以 $ x^{T}$ , 得到 $ x^{T} A^{T} A x=0$ 。则有 $ (A x)^{T}(A x)=0 $, 即$ \\|A x\\|=0$ 。所以得到 $ A x=0$ 。 所以, $ A^{T} A x=0 $ 的解都为 $ A x=0$ 的解。
所以 $ A x=0$ 和 $ A^{T} A x=0 $ 有相同的解空间。所以 $ r(A)=r\left(A^{T} A\right) $, 同理有, $ r\left(A^{T}\right)=r\left(A A^{T}\right)$ , 于是有:
$r\left(A A^{T}\right)=r\left(A^{T}\right)=r(A)=r\left(A^{T} A\right)$
b. 证明: $ A^ A$ 和 $ A A^$ 拥有相同的非零特征值, 且特征向量间存在制约关系。
$A^ A x=\lambda x$
将上式两边左乘一个矩阵 $ A$ 有
$A A^(A x)=\lambda(A x)$
那当 $ x \neq 0$ 时, $ A x$ 是否也是非 $0$ 向量?
因为 $ A x=0$ 和 $ A^{T} A x=0$ 同解, 所以要证明 $ A x \neq 0$ , 只需䨐证明 $ A^{T} A x \neq 0$ , 因为
$A^ A x=\lambda x \neq 0 \Rightarrow A x \neq 0$
SVD计算举例
这里们用一个简单的矩阵来说明奇异值分解的步骤。们的矩阵A定义为：
$A=\left(\begin{array}{ll}0 \& 1 \\1 \& 1 \\1 \& 0\end{array}\right)$
首先，们先求出 $A^ A$ 和 $A A^ $ :
$\begin{array}{l}A^{T} A=\left(\begin{array}{lll}0 \& 1 \& 1 \\1 \& 1 \& 0\end{array}\right)\left(\begin{array}{ll}0 \& 1 \\1 \& 1 \\1 \& 0\end{array}\right)=\left(\begin{array}{ll}2 \& 1 \\1 \& 2\end{array}\right) \\A A^{T}=\left(\begin{array}{ll}0 \& 1 \\1 \& 1 \\1 \& 0\end{array}\right)\left(\begin{array}{lll}0 \& 1 \& 1 \\1 \& 1 \& 0\end{array}\right)=\left(\begin{array}{lll}1 \& 1 \& 0 \\1 \& 2 \& 1 \\0 \& 1 \& 1\end{array}\right)\end{array}$
然后，求出 $A^ A$ 和 $A A^$ 的特征值和特征向量：
$A^ A$ 的特征值和特征向量 :
$\lambda{1}=3 ; \quad v{1}=\left(\begin{array}{c}\frac{1}{\sqrt{2}} \\\frac{1}{\sqrt{2}}\end{array}\right) ; \lambda{2}=1 ; \quad v{2}=\left(\begin{array}{c}\frac{-1}{\sqrt{2}} \\\frac{1}{\sqrt{2}}\end{array}\right)$
$A A^$ 的特征值和特征向量:
$\lambda{1}=3 ; \quad u{1}=\left(\begin{array}{c}\frac{1}{\sqrt{6}} \\\frac{2}{\sqrt{6}} \\\frac{1}{\sqrt{6}}\end{array}\right) ; \lambda{2}=1 ; \quad u{2}=\left(\begin{array}{c}\frac{1}{\sqrt{2}} \\0 \\\frac{-1}{\sqrt{2}}\end{array}\right) ; \lambda{3}=0 ; \quad u{3}=\left(\begin{array}{c}\frac{1}{\sqrt{3}} \\\frac{-1}{\sqrt{3}} \\\frac{1}{\sqrt{3}}\end{array}\right)$
其次，们利用 $A v=\sigma u_$, $\quad i=1,2$ , 求奇异值;
$\begin{array}{l}\left(\begin{array}{cc}0 \& 1 \\1 \& 1 \\1 \& 0\end{array}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2}} \\\frac{1}{\sqrt{2}}\end{array}\right)=\sigma{1}\left(\begin{array}{c}\frac{1}{\sqrt{6}} \\\frac{2}{\sqrt{6}} \\\frac{1}{\sqrt{6}}\end{array}\right) \Rightarrow \sigma{1}=\sqrt{3} \\\left(\begin{array}{cc}0 \& 1 \\1 \& 1 \\1 \& 0\end{array}\right)\left(\begin{array}{c}\frac{-1}{\sqrt{2}} \\\frac{1}{\sqrt{2}}\end{array}\right)=\sigma{2}\left(\begin{array}{c}\frac{1}{\sqrt{2}} \\0 \\\frac{-1}{\sqrt{2}}\end{array}\right) \Rightarrow \sigma{2}=1\end{array}$
当然，这一步也可以用 $\sigma=\sqrt{\lambda}$ 直接求出奇异值为 $\sqrt{3}$ 和 $1$。
最后，们得到A的奇异值分解为 :
$A=U \Sigma V^{T}=\left(\begin{array}{ccc}\frac{1}{\sqrt{6}} \& \frac{1}{\sqrt{2}} \& \frac{1}{\sqrt{3}} \\\frac{2}{\sqrt{6}} \& 0 \& \frac{-1}{\sqrt{3}} \\\frac{1}{\sqrt{6}} \& \frac{-1}{\sqrt{2}} \& \frac{1}{\sqrt{3}}\end{array}\right)\left(\begin{array}{cc}\sqrt{3} \& 0 \\0 \& 1 \\0 \& 0\end{array}\right)\left(\begin{array}{cc}\frac{1}{\sqrt{2}} \& \frac{1}{\sqrt{2}} \\\frac{-1}{\sqrt{2}} \& \frac{1}{\sqrt{2}}\end{array}\right)$
原文创作：CBlair
原文链接：https://www.cnblogs.com/BlairGrowing/p/15343137.html
