一步步教你轻松学奇异值分解SVD降维算法

一步步教你轻松学奇异值分解SVD降维算法

(白宁超 2018年10月24日09:04:56 )

摘要：奇异值分解（singular value decomposition）是线性代数中一种重要的矩阵分解，在生物信息学、信号处理、金融学、统计学等领域有重要应用，SVD都是提取信息的强度工具。在机器学习领域，很多应用与奇异值都有关系，比如推荐系统、数据压缩（以图像压缩为代表）、搜索引擎语义层次检索的LSI等等。（本文原创，转载必须注明出处.）

目录 1 机器学习：一步步教你轻松学KNN模型算法 2 机器学习：一步步教你轻松学决策树算法 3 机器学习：一步步教你轻松学朴素贝叶斯模型算法理论篇1  4 机器学习：一步步教你轻松学朴素贝叶斯模型实现篇2  5 机器学习：一步步教你轻松学朴素贝叶斯模型算法Sklearn深度篇3
6 机器学习：一步步教你轻松学逻辑回归模型算法 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}.
$$