一步步教你轻松学奇异值分解SVD降维算法
(白宁超 2018年10月24日09:04:56 )
摘要:奇异值分解(singular value decomposition)是线性代数中一种重要的矩阵分解,在生物信息学、信号处理、金融学、统计学等领域有重要应用,SVD都是提取信息的强度工具。在机器学习领域,很多应用与奇异值都有关系,比如推荐系统、数据压缩(以图像压缩为代表)、搜索引擎语义层次检索的LSI等等。(本文原创,转载必须注明出处.)
目录 1 机器学习:一步步教你轻松学KNN模型算法 2 机器学习:一步步教你轻松学决策树算法 3 机器学习:一步步教你轻松学朴素贝叶斯模型算法理论篇1 4 机器学习:一步步教你轻松学朴素贝叶斯模型实现篇2 5 机器学习:一步步教你轻松学朴素贝叶斯模型算法Sklearn深度篇36 机器学习:一步步教你轻松学逻辑回归模型算法 7 机器学习:一步步教你轻松学K-means聚类算法 8 机器学习:一步步教你轻松学关联规则Apriori算法 9 机器学习: 一步步教你轻松学支持向量机SVM算法之理论篇1 10 机器学习: 一步步教你轻松学支持向量机SVM算法之案例篇2 11 机器学习: 一步步教你轻松学主成分分析PCA降维算法 12 机器学习: 一步步教你轻松学支持向量机SVM降维算法 更多文章请点击这里>> 奇异值分解原理 什么是奇异值分解(SVD)
奇异值分解
假设M是一个m×n阶矩阵,其中的元素全部属于域K,也就是实数域或复数域。如此则存在一个分解使得
$$ M_{m×n}=U_{m×m} \Sigma_{m×n} V^T_{n×n} $$
其中U是m×m阶酉矩阵;Σ是m×n阶非负实数对角矩阵;而\(V^T\),即V的共轭转置,是n×n阶酉矩阵。这样的分解就称作M的奇异值分解。Σ对角线上的元素\(Σ_i\),i即为M的奇异值。常见的做法是将奇异值由大而小排列。如此Σ便能由M唯一确定了。(虽然U和V仍然不能确定。)
V的列组成一套对\(M\)的正交"输入"或"分析"的基向量。这些向量是\(M^*M\)的特征向量。
U的列组成一套对\(M\)的正交"输出"的基向量。这些向量是\(MM^*\)的特征向量。
Σ对角线上的元素是奇异值,可视为是在输入与输出间进行的标量的"膨胀控制"。这些是\( MM^* \)及 \( M^* M \)的特征值的非负平方根,并与U和V的行向量相对应。
SVD 的计算方法 SVD 与特征值现在,假设矩阵 \( \mathbf M_{m\times n} \) 的 SVD 分解是 \( \mathbf M = \mathbf U\mathbf\Sigma\mathbf V^{\mathsf H}; \)那么,我们有
$$
\begin{aligned}
\mathbf M\mathbf M^{\mathsf H} &{}= \mathbf U\mathbf\Sigma\mathbf V^{\mathsf H}\mathbf V\mathbf\Sigma^{\mathsf H}\mathbf U^{\mathsf H} = \mathbf U(\mathbf\Sigma\mathbf\Sigma^{\mathsf H})\mathbf U^{\mathsf H} \\
\mathbf M^{\mathsf H}\mathbf M &{}= \mathbf V\mathbf\Sigma^{\mathsf H}\mathbf U^{\mathsf H}\mathbf U\mathbf\Sigma\mathbf V^{\mathsf H} = \mathbf V(\mathbf\Sigma^{\mathsf H}\mathbf\Sigma)\mathbf V^{\mathsf H}\
\end{aligned}
$$
这也就是说,\( \mathbf U \) 的列向量(左奇异向量),是\( \mathbf M\mathbf M^{\mathsf H} \) 的特征向量;同时,\( \mathbf V \) 的列向量(右奇异向量),是 \( \mathbf M^{\mathsf H}\mathbf M \) 的特征向量;另一方面,\( \mathbf M \) 的奇异值(\( \mathbf\Sigma \) 的非零对角元素)则是 \( \mathbf M\mathbf M^{\mathsf H} \) 或者 \( \mathbf M^{\mathsf H}\mathbf M \) 的非零特征值的平方根。
如何计算 SVD有了这些知识,我们就能手工计算出任意矩阵的 SVD 分解了;具体来说,算法如下
计算 \( \mathbf M\mathbf M^{\mathsf H} \) 和 \( \mathbf M^{\mathsf H}\mathbf M \);
分别计算 \( \mathbf M\mathbf M^{\mathsf H} \) 和 \( \mathbf M^{\mathsf H}\mathbf M \) 的特征向量及其特征值;
\( \mathbf M\mathbf M^{\mathsf H} \) 的特征向量组成 \( \mathbf U \);而 \( \mathbf M^{\mathsf H}\mathbf M \) 的特征向量组成 \( \mathbf V \);
对 \( \mathbf M\mathbf M^{\mathsf H} \) 和 \( \mathbf M^{\mathsf H}\mathbf M \) 的非零特征值求平方根,对应上述特征向量的位置,填入 \( \mathbf\Sigma \) 的对角元。
实际计算看看现在,我们来试着计算 \( \mathbf M = \begin{bmatrix}2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0\end{bmatrix} \) 的奇异值分解。计算奇异值分解,需要计算 \( \mathbf M \) 与其共轭转置的左右积;这里主要以 \( \mathbf M\mathbf M^{\mathsf H} \) 为例。
首先,我们需要计算 \( \mathbf M\mathbf M^{\mathsf H} \),
$$
\mathbf W = \mathbf M\mathbf M^{\mathsf H} = \begin{bmatrix}2 & 4 \\ 1 & 3 \ 0 & 0 \\ 0 & 0\end{bmatrix}\begin{bmatrix}2 & 1 & 0 & 0 \\ 4 & 3 & 0 & 0\end{bmatrix} = \begin{bmatrix}20 & 14 & 0 & 0 \\ 14 & 10 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix}.
$$