SVD分解算法

奇异值分解(Singular Value Decomposition，以下简称SVD)之前接触还是在老师的课本里…。最近在看nlp相关概念知识，里面有写算法是基于svd分解的。因此重新查找资料学习svd分解。它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。是很多机器学习算法的基石。

特征值分解

如果 $A_{n \times n}x_{n \times 1}=\lambda x_{n \times 1}$ 则称 $\lambda$ 是矩阵 $A$的特征值，向量$x$叫做特征向量。

我们求出了矩阵A的n个特征值λ1≤λ2≤…≤λn,以及这n个特征值所对应的特征向量{w1,w2,…wn}，，如果这n个特征向量线性无关，那么矩阵A就可以用下式的特征分解表示： $A=W \Sigma W^T$

其中W是这n个特征向量所张成的n×n维矩阵，而Σ为这n个特征值为主对角线的n×n维矩阵

般我们会把W的这n个特征向量标准化，即满足$\parallel w_i \parallel_2=1$, 或者说$w_i^T w_i=1$，此时W的n个特征向量为标准正交基，满足$W^T W = I $，即$W^T=W^-1$, 也就是说$W$为酉矩阵。

特征值分解只能对方阵进行分解。那么对于非方阵则需要进行SVD分解。

svd分解

对于矩阵$A_{m \times n}$ ，则它的SVD分解定义为: $A_{m \times n}=U\Sigma V^T$

其中$U$是一个$m \times m$的矩阵，$\Sigma$是一个$m \times m$的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，$V$是一个$n\times n$的矩阵。$U$和$V$都是酉矩阵，即满足$U^T U=I$,$V^T V=I$

$$A_{m \times n}^T A_{m \times n} = ( U\Sigma V^T )^T (U\Sigma V^T) = V\Sigma U^T USigma V^T = V\Sigma^2 V^T$$

所以$V$是$A_{m \times n}^T A_{m \times n}$的特征值分解矩阵

同理有$U$是$A_{m \times n} A_{m \times n}^T$的特征值分解矩阵

由于$\Sigma$只有主对角线非0，所以主对角线上的元素$\delta_i=\sqrt{\lambda_i}$ 其中$\lambda_i$是$A_{m \times n}^T A_{m \times n}$的特征值。