SVD奇异矩阵分解

阅读量：4936 次

发布时间：2019-06-11

本文共 2220 字，大约阅读时间需要 7 分钟。

奇异矩阵分解SVD

奇异矩阵分解的核心思想认为用户的兴趣只受少数几个因素的影响，因此将稀疏且高维的User-Item评分矩阵分解为两个低维矩阵，即通过User、Item评分信息来学习到的用户特征矩阵P和物品特征矩阵Q，通过重构的低维矩阵预测用户对产品的评分.SVD的时间复杂度是O(m3).

在了解奇异矩阵分解前，先要了解矩阵分解，矩阵分解就是特征值分解，特征值分解和奇异值分解的目的都是一样，就是提取出一个矩阵最重要的特征.先谈谈特征值分解吧：

一.特征值分解：

如果说一个向量v是方阵A的特征向量，将一定可以表示成下面的形式：

这时候λ就被称为特征向量v对应的特征值，特征值不改变向量的方向，只会对向量进行伸缩的长度变换，一个矩阵的一组特征向量是一组正交向量.特征值分解是将一个矩阵分解成下面的形式：

其中Q是这个矩阵A的特征向量组成的矩阵，Σ是一个对角阵，每一个对角线上的元素就是一个特征值.一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量后得到的向量，其实就相当于将这个向量进行了线性变换.特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多重要，而特征向量表示这个特征是什么，特征值分解也有很多的局限，比如说变换的矩阵必须是方阵.

二.奇异值分解：

特征值分解是一个提取矩阵特征很不错的方法，但是它只是对方阵而言的，在现实的世界中，我们看到的大部分矩阵都不是方阵，比如说有N个用户，每个用户对应M个物品，这样形成的一个N * M的矩阵就不可能是方阵，我们怎样才能描述这样普通的矩阵呢的重要特征呢？奇异值分解可以用来干这个事情，奇异值分解是一个能适用于任意的矩阵的一种分解的方法：

设 A 为一个 $m\times n$ 阶实矩阵， $r=\mathrm{rank}A $，SVD 具有以下形式：

　　　　$A=U\Sigma V^T$

其中 U 是 $m\times m$ 阶， V 是 $n\times n $阶， $\Sigma$ 是 $m\times$ n 阶.特别的是，方阵 U 和 V 都是实正交矩阵(orthogonal matrix)，也就是说， $U^T=U^{-1}$ ，$ V^T=V^{-1}$， $\Sigma$ 是(类)对角矩阵，对角线上的值对应于对角矩阵的特征值，(类)对角矩阵上是奇异值，

图示可以帮助我们了解SVD 的矩阵结构. SVD 最特别的地方是 $\Sigma$ 的多数元为零，图中的白色区块以及黄色区块的非对角元皆为零.

令 U 的行向量(column vector)为$ \mathbf{u}_i $， $i=1，\ldots，m $， V 的行向量为$ \mathbf{v}_j $，$ j=1，\ldots，n $，$ A=U\Sigma V^T$ 可以表示为 r 个秩-1 (rank-one) 矩阵之和：

上式指出 A 仅由 U 的前 r 个行向量(以 $U_r $表示)，$ V^T $的前 r 个列向量(以 $V_r^T$ 表示)，以及 $\Sigma$ 的左上 $r\times r$ 分块决定(以 $\Sigma_r$ 表示)，矩阵 A 总共有 $m\times n $个元，$ U_r$ 有 $m\times r $个元， $V_r^T$ 有$ r\times n$ 个元，$ \Sigma_r$ 则只需储存主对角的 r 个非零元. 若以SVD 形式储存，总计有 $(m+n+1)\times r $个元. 当 r 远小于 m 和 n 时，利用矩阵的SVD 可以大幅减少储存量.