SVD奇异值分解
特征值分解
设矩阵$\textbf{A}$是$n \times n$的实对称矩阵，则存在正交矩阵$\textbf{U}$，使得：
其中，$\Lambda=diag(\lambda_1,\lambda_2,\ldots \lambda_n$是以 的特征值为对角线元素的对角矩阵，$\textbf{U}=(u_1,u_2,\ldots u_n)$，$u_i$为对应的特征向量。
由于$\textbf{U}$的正交性，上述描述等价于：
奇异值分解
特征值分解是针对方阵而言，那么对于普通的$m \times n$矩阵$\textbf{A}$，有没有分解的方法呢？
定义矩阵的奇异值分解（Singular Value Decomposition，SVD）为：
其中：
$\textbf{A}$为$m \times n $的矩阵
$\Sigma$为$ r \times r$的对角矩阵$diag(\sigma_1,\sigma_2,\ldots，\sigma_r)$其中$r=rank(\textbf{A})$
$\textbf{U}$为$m \times m$的正交方阵，即左奇异向量矩阵
$\textbf{V}$为$n \times n$的正交方阵，即右奇异向量矩阵
如何求解U、V？
考虑到$\textbf{A} \textbf{A} ^{T}$为实对称矩阵，同时$\textbf{V}$为正定阵，我们计算出来$\textbf{A} \textbf{A} ^{T}$。就可以把$\textbf{V}$消掉：
所以，我们就可以先计算出来$\textbf{A} \textbf{A} ^{T}$的特征值和对应的特征向量，这些特征向量就是构成$\textbf{U}=(u_1,u_2,\ldots u_n)$的列向量$u_1,u_2,\ldots u_n$,即左奇异向量。
同理，计算出来 $\textbf{A} ^{T}\textbf{A}$的特征值和对应的特征向量，这些特征向量就是构成$\textbf{V}=(v_1,v_2,\ldots v_n)$的列向量$v_1,v_2,\ldots v_n$,即右奇异向量。
如何求解$\Sigma$?
首先，$\textbf{A} \textbf{A} ^{T}$或者是必为半正定矩阵，原因如下：对于任意对任意向量 x，我们有：
因此，矩阵 $AA^T $是半正定矩阵,其特征值$\lambda_1,\lambda_2,\ldots,\lambda_r$必定大于等于0。
注意到（4）式中，出现的$\Sigma ^2$，我们就可以得到$\Sigma ^2$是由$\textbf{A} \textbf{A} ^{T}$对应特征值为对角线元素构成的对角阵，于是，可以先求出来$\textbf{A} \textbf{A} ^{T}$的若干特征值$\lambda_1,\lambda_2,\ldots,\lambda_r$(因为$rank(\textbf{A})=rank(\textbf{A}\textbf{A} ^{T})$)，这些特征值是$\Sigma ^2$的对角线元素，对其开方，就可以得到$\Sigma$的对角线元素$\sigma_1,\sigma_2,\ldots,\sigma_r$,即：
值得注意的是，由于矩阵$\textbf{A}$不一定是方阵，所以求出来的$\Sigma $矩阵也未必是方阵，而是一个和$\textbf{A}$行数和列数相同的矩阵。即使$\textbf{A}$是方阵，也未必满秩，所以我们求出来的$\sigma_1,\sigma_2,\ldots,\sigma_r$仅仅是$\Sigma$的左上角的一部分，需要用$0$填充为$m \times n$矩阵，就得到了最后的$\Sigma$
