SVD分解算法  

admin  

奇异值分解(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}$的特征值。