23、奇异值分解svd

本章内容包含了：

• SVD的公式
• SVD的通用计算方法
• SVD的手解方法
• 解SVD常遇见的疑问
• 在Matlab、OpenCV求解SVD的命令
• SVD的作用
• SVD的应用场景
• SVD和推荐系统、协同过滤和相似度的初步认识
• SVD网上优秀的学习文章和书籍

关于奇异值分解，网上优秀、详细的文章枚不胜举，其深度又有不同，我仅仅算是略微知晓，今我将认识的奇异值分解用通俗、简练的语言描述Singular Value Decomposition最重要的部分和入门初学的部分。

本人写这篇文章参考过十几二十篇关于SVD的文章和书籍，

关于书籍我推荐：

《Matrix Analysis》《机器学习实战》《矩阵分析》《线性代数及其应用》

关于文章我推荐：

（原理详解和推导文——推荐：）

奇异值分解(SVD)原理详解及推导 - CSDN博客​blog.csdn.net/zhongkejingwang/article/details/43053513

（SVD和PCA主成份分析、LSI潜在语义索引——推荐：）

强大的矩阵奇异值分解(SVD)及其应用 - liangflying - 博客园​www.cnblogs.com/liangflying/archive/2012/09/25/2701148.html

（实验和对应的图像——推荐：）

（奇异值分解的几何意义——推荐：）

奇异值分解(SVD) --- 几何意义 -jiangwen127-ChinaUnix博客​blog.chinaunix.net/uid-20761674-id-4040274.html

（其它文章——推荐：）

奇异值分解（SVD）详解 - CSDN博客​blog.csdn.net/seamanj/article/details/18444639

（SVD的众多求法（英文版）：）

奇异值分解是什么

奇异值分解的求解方法

对于一个矩阵A，常有分解式： $A=PD{P}^{-1}$A=PDP^{-1} ，

但并不是所有的矩阵A都能够这么分解，其中P可不可逆，A是否为方阵，往往决定了A矩阵能否分解，

而在奇异值分解中，我们将A分解为： $A=U\mathrm{\Sigma }{V}^H$A=U\Sigma V^{H} （H为共轭，另有用*号替代H。共轭代表在复数空间进行“数字共轭”和“转置”，所以在实数空间内，H表现为转置T。）

以上这条式子就是奇异值分解SVD的公式。

其中U被称为左奇异向量，V被称为右奇异向量。

对于 $\mathrm{\Sigma }$\Sigma ，是一个包含了“奇异值”的对角矩阵。

其主对角线若有n个位置，而 $A{A}^T$AA^{T} 的特征值若有r个，那么 $\mathrm{\Sigma }$\Sigma 的对角线上就有(n-r)个“奇异值”，这是考虑到主对角线上的奇异值除了求得的，在主对角线上其余为0的情况。

这些“奇异值”就是 $A{A}^T$AA^{T} 或者 $A^{T}A$A^{T}A 的特征值再开一次根号。（这两者的特征值是一致的）（注意，这些特征值开一次根号后，需要降序排列在 $\mathrm{\Sigma }$\Sigma 的主对角线上。）

对于V，它是 $A^{T}A$A^{T}A 的特征向量。注意：在最后的SVD公式中，需要将V进行转置。

对于U，它是 $A{A}^T$AA^{T} 的特征向量。

所以，第一种“通用的求解方法”是：

求出 $A^{T}A$A^{T}A 和 $A{A}^T$AA^{T} 各自的特征向量，还有共同的特征值，

各自的特征向量就分别是V和U，

将特征值开根号后就是奇异值降序排列就是 $\mathrm{\Sigma }$\Sigma ，

注意的是， $\mathrm{\Sigma }$\Sigma 中的奇异值所对应U和V的特征向量需要一一对应。（这就好像求特征向量和特征值时要一个一个对应准确一样。）

而第二种方法是“手解的方法”，只适用于低维度的矩阵解题验证，当数字很好时，会很快，当数字不太友好时，可能计算步骤会很麻烦：

其思想是

1、V是A行空间的基向量，U是A列空间的基向量；

2、单位化部分行向量和单位化部分列向量，其余向量以单位正交的方式求解而出，如此，形成U和V。

其主要麻烦的来源在于：有些地方需要做施密特正交化。

具体的方法在下面的图片题目中会详细介绍，

但要额外提一下手解中U和V的关系，其实通用的求解方法也同样存在这种关系，

$u_n=\frac{1}{{\sigma }_n}A{V}_n$u_{n}=\frac{1}{\sigma _{n}}AV_{n}

比较两种SVD的计算方法，其实在上面已经隐约表达了我想推荐使用“通用的求解方法”，

因为“手解”实在局限于理论和数学题目了。

使用“通用的求解方法”当然你可以自己手动求解，也可以使用python的numpy库或者maltab等科学计算软件进行计算。

现在我们先来看一下具体怎么利用SVD公式分解矩阵。在题目过后，再给出关于奇异值的用处和应用场景。

计算的具体方法

先看下通用公式对矩阵做SVD分解：

在例题2中出现了最后的矩阵需要再绝对值才等于原矩阵。

为什么会这样。在下一段中，我再说明白。

但现在，先说明：

当SVD结果的矩阵出现以下这两种情况时：

1、需要整个矩阵添加相反的正负号才等于原矩阵；

2、SVD求出的矩阵中某一列（多列也一样）需要添加相反的正负号才等于原矩阵；

以上两种情况都认为：你求解SVD成功，求的这个SVD和原矩阵一致。

现在先来看看手解SVD的作法：

备注：

本来我想将例1和2都写上手解发上来，但觉得太简单了，没有特别大的必要。

例题1和2我都求过手解，答案和原矩阵一模一样，如果你再计算中发现有问题，我非常肯定你肯定是计算哪里出错了。

（在例题1和2中手解过程中没有用到施密特正交化。）

下面分析一下我发现在求SVD中常遇见到的几种问题。

解SVD常遇见的疑问

1、需要添加正负符号问题

在例题2中出现了最后的矩阵需要再绝对值才等于原矩阵，或者出现某一列需要添加正负正反的符号才等于原矩阵，为什么会这样？

答：原因是你所用的计算软件对“它”动的毛手毛脚。

我非常肯定这一点。在查阅网上大量相似问题又最后无解，自己在matlab中发现：如果你只是一步一步求解 $A{A}^T$AA^{T} 或者 $A^{T}A$A^{T}A ，最后将结果分别依照公式拼凑上去，那么问题就在你求解 $A{A}^T$AA^{T} 和 $A^{T}A$A^{T}A 的特征向量时，计算软件有时会给某一列添加和你预想结果完全每一个都相反的符号。

所以在最后得出的计算结果中，将会出现某一列或者整个矩阵出现需要添加正负号才等于原矩阵的原因。

但是，这并不干扰你求解SVD的正确性。

它给你添加的相反符号也没有错。

因为它们本质是“特征向量”，本质是线性或非线性方程的基础解系，只要它是相应的线性方程组的基础解系就没问题。同一特征值的特征向量的非零线性组合，仍然是这个特征值的特征向量。比如，若 x 是方阵A某个特征值对应的特征向量，则kx 也是A对应于该特征值的特征向量。（k取正数或者负数，不取0）在之前的章节里，很清楚得说明白了k是基础解系的k倍，基础解系的k倍，无论k几倍都是某个特征值的特征向量，它们都存在在一条轴上，一条由同一个方向上各个长短不同的特征向量组成的“旋转轴”。

所以对某一列向量，或者所有的列向量添加相反的符号（乘于-1），得到的SVD分解结果都是正确的。

但若非整个列向量取相反符号，而是仅仅存在某一个分量有符号问题，那就是你求解中出现了问题。

但是！这种情况却有一个例外，请参考下一点 2

2、“求错”的地方刚好撞见“转置”

比如，在麻省理工大学Gilbert Strang教授讲的《线性代数》的奇异值分解那一课，他出现错误的问题在于，

“求错”的地方刚好撞见“转置”，

V矩阵正确的符号应该是：

正 负

正 正

他求成了：

正 正

正 负

本来这样也是没错的，因为在1中，我说特征向量kx和x一样，在上面两个矩阵中，下面的列2只不过乘于-1就等于上面的列2，本来是正确的，

但是问题就在于，V矩阵最后在SVD公式里需要转置，而转置的位置刚好就是将E12变到E21，将E21变到E12，所以原本在属于那一列中没有错误的计算，转置后就错误了。

解决的方法并不是手解，我想没人蠢到用手解解一个"万阶矩阵"吧？有的话请告诉我。。。

解决的方法在下一段将出现。（下一段为：计算软件求解SVD的要注意的问题）

3、其它常见出错的问题

有可能是V没有进行转置：反正我是看到Gilbert Strang教授那一课中，其实不仅没有发现“错误点”在转置位置，而且，他还忘了对V进行转置。（所幸当时那个矩阵转不转置两者都一样，所以他忘了也没什么。解错，这不毫不奇怪，但可笑是，国内的相关文章上都依照他错误的方式去解，不仅没有解答真正的本质在于转置位置，就连V需要转置这么基础的也没有一个人记得。我看过很多文章，大家都生搬硬抄直接将黑板的写上去，完全不怀疑他有没有可能写错了。真是读死书。也怪不得国外有Wolframalpha、Mathpad、Mathematics等等软件，国内却只能在每个软件的评论区喊着“有没有中文版？”）

有可能是U的符号出现错误

在多次实验当中，我发现如果最后的数字出现了错误，那么很可能是因为左乘矩阵出现了问题，在放到这个SVD的例子当中，SVD的左乘矩阵就是U。

也就是可以这么总结：

如果只是列向量的正负出现问题，要么你是在V上出心大意忘了添加某个符号，要么就是你刚好碰上"错误点"和"转置位置"；

如果你发现整个SVD结果的矩阵数字都出现问题了，数字都完全不相同了，而且可能正负号都不按规律来，那么，首先检查左乘矩阵U矩阵的正负符号。

计算软件求解SVD的要注意的问题

首先，用哪一款软件计算SVD都不是重点，重点是：不要一个一个去求，即是不要去求 $A{A}^T$AA^{T} 和 $A{A}^T$AA^{T} ，然后再一一去求各自的特征向量组成V、U。

千万不要这样去求！！！

因为有可能出现上面出现常见问题1中描述的，当正确而又不恰当的特征向量的分量出现在V的E12转置位置时，有问题出现。

所以，我们在用计算软件求解SVD时，请直接使用求解SVD的命令。而不要一一求解，再自己去组合计算。

例如：

在Matlab当中，使用：

[b c d]=svd(x)

在OpenCV当中，使用：

void cvSVD( CvArr* A, CvArr* W, CvArr* U=NULL, CvArr* V=NULL, int flags=0 )

关于奇异值的一点想法：

当应用矩阵A的奇异值分解时，多数涉及方程Ax=b的数值计算要尽可能的可靠。两个正交矩阵U和V不影响向量的长度和两个向量的夹角。数值计算中的任何不稳定因素都与 $\mathrm{\Sigma }$\Sigma 有关。如果A的奇异值非常大或者非常小，舍入误差几乎是不可避免的。此时，知道 $\mathrm{\Sigma }$\Sigma 和 $V$V 中的元素对分析误差特别有用。

注意：我们应避免 $A^{T}A$A^{T}A 的计算，原因是任何A中元素的误差在 $A^{T}A$A^{T}A 中被平方。存在快速迭代的方法，可计算精确到很多位数的矩阵A的奇异值和奇异向量。（进一步阅读《Matrix Analysis》 by Roger A.Horn，Charles R. Johnson .1985 ) ,pp.414-445）

奇异值分解常用来估计矩阵的秩。

在一般情形下，A的秩对A中元素的微小变化很敏感，如果用计算机对矩阵A作行简化，明显矩阵A的主元列数目的计算方法效果不好，舍入误差导致满秩的阶梯矩阵。

实际上，估计大矩阵的秩时，最可靠的方法是计算非零奇异值的个数，在这种情况下，特别小的非零奇异值在实际计算中常假定为零，矩阵A的有效秩是剩余非零奇异值的数目。

为什么要做矩阵分解

在很多情况下，数据中的一小段携带了数据集中的大部分信息，其它信息要么是噪声，要么是毫无相关的信息。线代里，有很多矩阵分解的技术，矩阵分解能够将原始矩阵表示成易于处理的形式，常常将高维矩阵转化为低维的空间，对于其中一种常见的矩阵分解级数为SVD。

SVD是矩阵分解的一种类型，而矩阵分解就是将数据矩阵分解为多个独立部分的过程。

SVD的其中一个作用就是通过在低维空间下计算相似度，我们提高了在推荐引擎的效果。

SVD作用的实质

利用SVD实现，我们能用小得多的数据集来表示原始数据集。这样实际上是去除了噪声和冗余信息。

当我们试图节省空间时，去除噪声和冗余信息是很崇高的目标，

但是，在这里，SVD则却是让我们从数据中抽取信息。

即是我们可以把SVD看成是从有噪声的数据中抽取相关特征。

SVD的优缺点：

优点：简化数据，去除噪声，提高算法的结果。

缺点：数据的转换可能难以理解。

适用数据类型：数值型数据。

应用场景

推荐系统的应用场景

餐馆有中式，美式，日式，韩式，牛排，素食等等，而这些类别还常混合，比如子类别中式素食。那如何才知道有多少类餐馆？

我们可以对记录用户关于餐馆观点，对此数据进行处理，并从中提取背后的因素。

这些因素，可能会和餐馆类别、某个配料，某几个菜色，或其它“某个对象”一致。

然后我们就可以利用这些因素来估计人们对没有去过的餐馆的看法。

而提取这些信息的方法称为奇异值分解（SVD）。

以上说的这个场景，就是SVD在推荐系统当中的使用。

对于 $A=U\mathrm{\Sigma }{V}^H$A=U\Sigma V^{H} ，

举个例子，

在大众点评的APP餐馆里，

包含了用户对“手撕牛肉”，“烤牛肉”的1~5星的评级，也包含了用户对“寿司”“日式炸鸡”“北海道白色恋人芝士焗饭”的1~5星的评级。（1、注意：类别“菜色”）

很明显：“手撕牛肉”，“烤牛肉”是“美式菜”，

“寿司”，“日式炸鸡，”“北海道白色恋人芝士焗饭”是“日式菜”。

这五个菜色被归为两大类：即“美式菜”、“日式菜”。（2、注意：类别“餐馆类型”）

有名字为：张1、张2、张3、李4、李5——这五位大仙；（3、注意：类别“用户”）

在大众点评中，我作为唯一一个能娶到白富美的程序员发现，只有张1、张2、张3对“手撕牛肉”，“烤牛肉”进行评级，而对剩下的三种菜色从未评级！

那么我们可以得出张1、张2、张3三位大仙，对“美式菜”——感兴趣！而对“日式菜”无感。

而恰好得，我作为唯一一个能娶到白富美的程序员发现，李4、李5只对“寿司”“日式炸鸡”“北海道白色恋人芝士焗饭”进行过评级，对其它两道菜色并未涉及，

那么我们可以得出李4、李5两位大仙，对“日式菜”——感兴趣！而对“美式菜”无感。

基于此，我们得出结论：

对于一个大的人群，可以归类为两类，为：1️⃣张1 2 3，2️⃣李4 5，

对于大量的菜色，可以归类为两类，为：“美式菜”、“日式菜”，

所以：

我们就将“美式菜”、“日式菜”作为 $\mathrm{\Sigma }$\Sigma 这个二维矩阵。

将用户代表的评级作为 $V$V 这个矩阵。

将餐馆里的菜色作为 $U$U 这个矩阵。

记住：无论是 $\mathrm{\Sigma }$\Sigma 还是 $V$V ，我们是在大量数据里，基于共同特征来归类出某一个组和另一个组等等其它组。（在这里，我们是基于评价中一组人对一组菜有感，对另一组菜无感；而另一组人对一组菜却反而有感，对另一组菜却反而无感。如此，区分出组和类。）

补充：

$V^T$V^{T} 矩阵将所代表的用户评级，映射到， $\mathrm{\Sigma }$\Sigma 所代表“美式菜”、“日式菜”的类别空间上去。

$U$U 矩阵将所代表的具体菜色，映射到， $\mathrm{\Sigma }$\Sigma 所代表的“美式菜”、“日式菜”的类别空间上去。

最后，我们来回忆上面提到的一句话：

数值计算中的任何不稳定因素都与 $\mathrm{\Sigma }$\Sigma 有关。如果A的奇异值非常大或者非常小，舍入误差几乎是不可避免的。此时，知道 $\mathrm{\Sigma }$\Sigma 和$V$V中的元素对分析误差特别有用。

我想，在这里再回忆这句话，会有更深刻的理解。

在文末

SVD是一种强大的降维工具，我们可以利用SVD来逼近矩阵并从中提取重要的特征。再通过保留矩阵80%-90%的能量，又或者只保留前2千-3千的奇异值（当奇异值上万时），来实现得到重要的特征和去除其余噪声。

SVD在很多个方面都有应用，比如在隐性语义分析上，又比如在推荐引擎将物品推荐给用户。在推荐引擎中，协同过滤是一种在推荐引擎中实现推荐功能的方法，它将基于用户喜好或者行为数据的推荐的实现方法。协同过滤的核心是相似度计算方法（一种是我们利用欧式距离来计算，再利用—— $相似度=\frac{1}{1+距离}$相似度= \frac{1}{1+距离} ，算出区间为：0≤相似度≤1的相似度；另一种方法是皮尔逊相关系数计算距离。）有很多相似度计算方法都可以用于计算物品或者用户之间的相似度。而通过在低维空间下，计算相似度，我们提高了在推荐引擎的效果。

（完）