(七)奇异值分解

线性代数 机器学习基础

---

SVD的代数表达式

之前大致总结线性代数中的各个重要的知识点，现在，有了前边的简单总结(有些还需要后续逐步完善)，对于SVD的说明也就简单了。奇异值分解(Singular Value Decomposition)可以被应用到所有的实数矩阵(当然复数矩阵也可以进行奇异值分解，但是这里只讨论实数矩阵)当中，不像特征值分解只能够应用于方阵，奇异值分解可以应用于任意$m \times n, m \neq n$的矩阵。

对于任意$m \times n, m \neq n$的实数矩阵$A$来说，通过前边的总结我们已经知道，$n \times n$的实对称矩阵可以找到$n$个标准正交的特征向量，而再结合之前矩阵的转置的描述，可以知道$AA^{T}$和$A^{T}A$都是实对称矩阵，所以我们总是可以把它们对角化成如下所示的形式：

$$AA^{T}=U\Lambda_{1} U^{T} \tag{1}$$ $$A^{T}A=V\Lambda_{2} V^{T} \tag{2}$$ 的形式，其中，$U$是由$m$个标准正交的向量构成的方阵，$V$是由$n$个标准正交的向量构成的另外一个方阵，虽然矩阵$A$不一定为实对称矩阵，但是它和它的转置进行左乘或者是右乘却可以得到这样的实对称矩阵，所以可以得到上边的两个表达等式。
奇异值分解的标准定义如下：
$$A_{m \times n}=U_{m \times m}\Sigma_{m \times n}V^{T}_{n \times n} \tag{3}$$ 就单从等式1和2好像无法给出等式3，但是如果以等式3成立的情况下推导出等式1和2却是容易的，比如此时此刻有
$$AA^{T}=U\Sigma_{m \times n}V^{T}V\Sigma^{T}_{m \times n}U^{T}=U\Sigma_{m \times n}\Sigma^{T}_{m \times n}U^{T} \implies \Lambda_{1}=\Sigma_{m\times n}\Sigma^{T}_{m\times n} \tag{4}$$ 同时
$$A^{T}A=V\Sigma_{m \times n}^{T}U^{T}U\Sigma_{m \times n}V^{T}=V\Sigma^{T}_{m \times n}\Sigma_{m \times n}V^{T} \implies \Lambda_{2}=\Sigma^{T}_{m\times n}\Sigma_{m\times n} \tag{5}$$ 那样，很容易可以得到等式1和2，不过如果在等式1和2满足的情况下，似乎还需要
$$\Lambda_{1}=\Sigma_{m\times n}\Sigma^{T}_{m\times n}, \Lambda_{2}=\Sigma^{T}_{m\times n}\Sigma_{m\times n} \tag{6}$$ 也满足的情况下，才可以推导出等式3，但是这里也没有说为什么$\Lambda_{1}$和$\Lambda_{2}$会有这样的联系，但其实直接通过等式1和2就可以推导出3了，等式6只不过是副产品罢了，把等式2做一下变换可以得到
$$(A^{T}A)V=V\Lambda_{2} \tag{7}$$ 若把两边乘以矩阵$A$，那么
$$(AA^{T})(AV)=(AV)\Lambda_{2} \tag{8}$$ 但是从等式1又可以得到
$$(AA^{T})U=U\Lambda_{1} \tag{9}$$ 它们之间似乎具有某种联系，但是还不能画上等号。对于等式7，如果两边都乘以$V^{T}$可以得到
$$(AV)^{T}AV=\Lambda_{2} \tag{10}$$ 由于$\Lambda_{2}$只有对角线上有元素，所以可以知道，矩阵$AV$的列向量之间是两两正交的，而且这些列向量的平方和，刚好都在对角矩阵$\Lambda_{2}$的对角线上，即$AV$一共有$n$个这样的列向量，长度的平方分别位于$\Lambda_{2}$的对角线元素上。但这又可以说明什么呢？这个时候再看等式8，此时矩阵$AV$的列向量实际上都是矩阵$AA^{T}$的特征向量，而且两两正交，只不过并非标准正交的罢了。这个时候，对比等式8和9，等式9中的$U$是标准正交的矩阵，此时，如果把$AV$标准正交化，不久可以从$AV$得到$U$了吗？或者说，把矩阵$U$乘以各个长度，不就得到了矩阵$AV$了吗？我们从式10已经知道了矩阵$AV$的长度的平方实际上都在矩阵$\Lambda_{2}$的对角线上了，所以利用它不久可以得到关系了吗？但是维度关系不正确啊！$U$是$m \times m$的矩阵，但是$AV$是$m \times n$的矩阵，它们之间没办法取得关联，但是从另外一个角度来说，本质上，等式9中$AA^{T}$的特征向量实际上在$A$的列空间中，对于$m \times n, m \neq n$的矩阵，它的秩$r \leq m, r \leq n$，所以$U$中的至少$m-r$个特征向量是在$A$的零空间里边的(选择这些在零空间里边的特征向量可以构成完整的$m$个向量)，也就是说，我们可以构造一个$m \times n$的对角矩阵$\Sigma_{m \times n}$，它在$r \times r$的左上角区域的对角线上包含长度，其它元素均为$0$，这个时候，结合$AV$是一个$n$个列向量之间正交的矩阵，它的列空间本质上也是$A$的列空间，所以如果$r \lt n$，那么必然$AV$中会有一些列是全零，不过这没有关系，如果我们的这$r$个非零向量的长度依次摆放到$\Sigma_{m \times n}$的$r\times r$个对角线上，那么它们的单位向量构成的矩阵$U$完全可以通过乘以这个矩阵得到$AV$，即
$$AV=U\Sigma \tag{11}$$ 成立，需要注意的是，这里边$U$怎么摆放的完全就是可以自行定义的，只要对角矩阵跟着变就行了。通常会把长度越大的值放到越靠近左上角。

这样，上边就从实对称矩阵的性质出发，结合一个矩阵乘以它的转置可以得到对称矩阵，然后再利用行列空间的概念，以及代数表达式的技巧，得到了SVD的通用表达式。我这里边的角度，主要是从特征分解到实对称矩阵，然后到奇异值分解这个整个过程出发，得到了SVD的标准表达式，和一般直接上来就给出SVD定义不同，这样我认为可以更为清晰的反映出整个脉络以及SVD的由来等。

SVD在数据压缩上的应用

SVD的一个最常用的地方其实是数据压缩降维，SVD可以用下图来直观的描述：

当一个矩阵经过SVD后，中间得到的对角矩阵如果仅有前边$r \times r$区域的对角线上的元素数值比较大，其它的都接近$0$，那么实际上，完全可以省略掉其它的元素，此时：

$$A=U\Sigma V^{T} \approx U_{m \times r}\Sigma_{r \times r}V^{T}_{r \times n} \tag{12}$$ 也就是说，相比于原来$m\times n$个数据需要记录，我们可以通过SVD分解后，记录$(m\times r + r \times r + r \times n)=r(m + n + r)$个数据即可，相当于减少了不必要的信息，但这也仅仅只是在$r$可以取得较小值的情况下才具有良好的压缩率。

@fsfzp888
2018 年 04月 15日