作者丨七月算法
奇异值剖析（Singular Value Decomposition）是线性代数中一种主要 的矩阵剖析，是在机械学习领域普遍 应用的算法,本文对奇异值剖析的看法举行 了先容 ，以图像举例诠释 了奇异值剖析的应用。
特征值和奇异值在大部门人的印象中，往往是停留在纯粹的数学盘算中。而且线性代数或者矩阵论内里 ，也很少讲任何跟特征值与奇异值有关的应用配景。
奇异值剖析是一个有着很显着 的物理意义的一种要领，它可以将一个较量 重大 的矩阵用更小更简朴的几个子矩阵的相乘来体现，这些小矩阵形貌 的是矩阵的主要 的特征 。就像是形貌 一小我私人 一样，给别人形貌 说这小我私人 长得浓眉大眼，方脸，络腮胡，而且带个黑框的眼镜，这样寥寥的几个特征，就让别人脑海内里 就有一个较为清晰 的熟悉 ，现实 上，人脸上的特征是有着无数种的，之以是 能这么形貌 ，是由于 人天生就有着很是好的抽取主要 特征的能力，让机械学会抽取主要 的特征，SVD是一个主要 的要领。
在机械学习领域，有相当多的应用与奇异值都可以扯上关系，好比做feature reduction的PCA，做数据压缩（以图像压缩为代表）的算法，尚有 做搜索引擎语义条理检索的LSI（Latent Semantic Indexing）
一、特征值与奇异值
特征值剖析和奇异值剖析在机械学习领域都是属于满地可见的要领。两者有着很细密 的关系，接下来谈判到特征值剖析和奇异值剖析的目的都是一样，就是提取出一个矩阵最主要 的特征。先谈特征值剖析。
1.1 特征值
若是 说一个向量v是方阵A的特征向量，将一定可以体现成下面的形式：
这时间 λ就被称为特征向量v对应的特征值，一个矩阵的一组特征向量是一组正交向量。特征值剖析是将一个矩阵剖析成下面的形式：
其中Q是这个矩阵A的特征向量组成的矩阵，Σ是一个对角阵，每一个对角线上的元素就是一个特征值。我这里引用了一些参考文献中的内容来说明一下。
首先，要明确的是，一个矩阵着实 就是一个线性变换，由于 一个矩阵乘以一个向量后获得的向量，着实 就相当于将这个向量举行 了线性变换。好比说下面的一个矩阵：
它着实 对应的线性变换是下面的形式：
由于 这个矩阵M乘以一个向量(x,y)的效果 是：
上面的矩阵是对称的，以是 这个变换是一个对x，y轴的偏向一个拉伸变换（每一个对角线上的元素将会对一个维度举行 拉伸变换，当值1时，是拉长，当值1时时缩短），当矩阵不是对称的时间 ，若是 说矩阵是下面的样子：
它所形貌 的变换是下面的样子：
这着实 是在平面上对一个轴举行 的拉伸变换（如蓝色的箭头所示），在图中，蓝色的箭头是一个最主要的转变 偏向（转变 偏向可能有不止一个），若是 我们想要形貌 好一个变换，那我们就形貌 好这个变换主要的转变 偏向就好了。反过头来看看之前特征值剖析的式子，剖析获得的Σ矩阵是一个对角阵，内里 的特征值是由大到小排列的，这些特征值所对应的特征向量就是形貌 这个矩阵转变 偏向（从主要的转变 到次要的转变 排列）。
思量 更一样平常 的非对称矩阵
很遗憾，此时我们再也找不到一组网格，使得矩阵作用在该网格上之后只有拉伸变换（找不到背后的数学缘故原由 是对一样平常 非对称矩阵无法保证在实数域上可对角化，不明确 也不要在意）。
我们退而求其次，找一组网格，使得矩阵作用在该网格上之后允许有拉伸变换和旋转变换，但要保证变换后的网格依旧相互垂直，这是可以做到的，如下图所示。
简言之，当矩阵是高维的情形 下，那么这个矩阵就是高维空间下的一个线性变换，这个变换也同样有许多的变换偏向，我们通过特征值剖析获得的前N个特征向量，那么就对应了这个矩阵最主要的N个转变 偏向。我们使用 这前N个转变 偏向，就可以近似这个矩阵（变换）。
也就是之前说的：提取这个矩阵最主要 的特征。总结一下，特征值剖析可以获得特征值与特征向量，特征值体现的是这个特征到底有多主要 ，而特征向量体现这个特征是什么，可以将每一个特征向量明确 为一个线性的子空间，我们可以使用 这些线性的子空间干许多的事情。不外，特征值剖析也有许多的局限，好比说变换的矩阵必须是方阵。
下面我们就可以自然过渡到奇异值剖析的引入。
1.2 奇异值
下面谈谈奇异值剖析。特征值剖析是一个提取矩阵特征很不错的要领，可是 它只是对方阵而言的，在现实的天下 中，我们看到的大部门矩阵都不是方阵，好比说有N个学生，每个学生有M科效果 ，这样形成的一个N * M的矩阵就不行能是方阵，我们怎样才气形貌 这样通俗 的矩阵呢的主要 特征呢？奇异值剖析可以用来干这个事情，奇异值剖析是一个能适用于恣意 的矩阵的一种剖析的要领：
假设A是一个N * M的矩阵，那么获得的U是一个N * N的方阵（内里 的向量是正交的，U内里 的向量称为左奇异向量），Σ是一个N * M的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’(V的转置)是一个N * N的矩阵，内里 的向量也是正交的，V内里 的向量称为右奇异向量），从图片来反映几个相乘的矩阵的巨细可得下面的图片
那么奇异值和特征值是怎么对应起来的呢？首先，我们将一个矩阵A的转置 * A，将会获得一个方阵，我们用这个方阵求特征值可以获得：
这里获得的v，就是我们上面的右奇异向量。此外我们还可以获得：
这里的σ就是上面说的奇异值，u就是上面说的左奇异向量。奇异值σ跟特征值类似，在矩阵Σ中也是从大到小排列，而且σ的镌汰 特此外快，在许多情形 下，前10%甚至1%的奇异值的和就占了所有 的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似形貌 矩阵，这里界说一下部门奇异值剖析：
r是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子：
右边的三个矩阵相乘的效果 将会是一个靠近 于A的矩阵，在这儿，r越靠近 于n，则相乘的效果 越靠近 于A。而这三个矩阵的面积之和（在存储看法来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵A，我们若是 想要压缩空间来体现原矩阵A，我们存下这里的三个矩阵：U、Σ、V就好了。
说句明确 话，称作「奇异值」可能无法顾名思义迅速明确 其本质，那咱们换个说法，称作「主特征值」，你可能就迅速了然了。
而奇异值剖析的几何寄义为：对于任何的一个矩阵，我们要找到一组两两正交单元向量序列，使得矩阵作用在此向量序列上后获得新的向量序列保持两两正交。
继续拿1.1节的例子进一步叙述 ，奇异值的几何寄义为：这组变换后的新的向量序列的长度。
奇异值的盘算是一个难题，是一个O(N^3)的算法。在单机的情形 下虽然是没问题的，matlab在一秒钟内就可以算出1000 * 1000的矩阵的所有奇异值，可是 当矩阵的规模增添 的时间 ，盘算的重大 度呈3次方增添 ，就需要并行盘算加入了。Google的吴军先生 在数学之美系列谈到SVD的时间 ，提及 Google实现了SVD的并行化算法，说这是对人类的一个孝顺 ，可是 也没有给出详细 的盘算规模，也没有给出太多有价值的信息。
着实 SVD照旧可以用并行的方式去实现的，在解大规模的矩阵的时间 ，一样平常 使用迭代的要领，当矩阵的规模很大（好比说上亿）的时间 ，迭代的次数也可能会上亿次，若是 使用Map-Reduce框架去解，则每次Map-Reduce完成的时间 ，都市涉及到写文件、读文件的操作。小我私人 推测Google云盘算系统 中除了Map-Reduce以外应该尚有 类似于MPI的盘算模子 ，也就是节点之间是保持通讯 ，数据是常驻在内存中的，这种盘算模子 比Map-Reduce在解决迭代次数很是多的时间 ，要快了许多倍。
Lanczos迭代就是一种解对称方阵部门特征值的要领（之前谈到了，解A’* A获得的对称方阵的特征值就是解A的右奇异向量），是将一个对称的方程化为一个三对角矩阵再举行 求解。按网上的一些文献来看，Google应该是用这种要领去做的奇异值剖析的。请见Wikipedia上面的一些引用的论文，若是 明确 了那些论文，也“险些”可以做出一个SVD了。
二、奇异值的直观应用
2.1 女神图片压缩
下面，咱们从女神上野树里（Ueno Juri）的一张像素为高度450*宽度333的照片，来直观明确 奇异值在物理上到底代表什么意义（请屏幕前的痴汉暂停舔屏）。
我们都知道，图片现实 上对应着一个矩阵，矩阵的巨细就是像素巨细，好比这张图对应的矩阵阶数就是450*333，矩阵上每个元素的数值对应着像素值。我们记这个像素矩阵为A 现在我们对矩阵A举行 奇异值剖析。直观上，奇异值剖析将矩阵剖析成若干个秩一矩阵之和，用公式体现就是：
若是 不知足 的话重新排列顺序即可，这无非是编号顺序的问题。既然奇异值有从大到小排列的顺序，我们自然要问，若是 只保留大的奇异值，舍去较小的奇异值，这样(1)式里的等式自然不再建设，那会获得怎样的矩阵——也就是图像？
效果 就是完全看不清是啥……我们试着多增添 几项进来：
再作图
隐约可以分辨这是短发伽椰子的脸……但照旧很模糊，事实 我们只取了5个奇异值而已。下面我们取20个奇异值试试，也就是(1)式等式右边取前20项组成
虽然尚有 些马赛克般的模糊，但我们总算能分辨出这是Juri酱的脸。当我们取到(1)式等式右边前50项时：
奇异值往往对应着矩阵中隐含的主要 信息，且主要 性和奇异值巨细正相关。每个矩阵A都可以体现为一系列秩为1的“小矩阵”之和，而奇异值则权衡了这些“小矩阵”对于A的权重。
2.2 图像去噪
在图像处置赏罚 领域，奇异值不仅可以应用在数据压缩上，还可以对图像去噪。若是 一副图像包罗噪声，我们有理由信托 那些较小的奇异值就是由于噪声引起的。当我们强行令这些较小的奇异值为0时，就可以去除图片中的噪声。如下是一张25*15的图像
但往往我们只能获得如下带有噪声的图像（和无噪声图像相比，下图的部门白格子中带有灰色）：
通过奇异值剖析，我们发现矩阵的奇异值从大到小划分为：14.15，4.67，3.00，0.21，……，0.05。除了前3个奇异值较大以外，其余奇异值相比之下都很小。强行令这些小奇异值为0，然后只用前3个奇异值结构新的矩阵，获得
可以显着 看出噪声镌汰 了（白格子上灰白相间的图案镌汰 了）。奇异值剖析还普遍 的用于主因素 剖析 （Principle Component Analysis，简称PCA）和推荐系统（如Netflex的影戏推荐系统）等。在这些应用领域，奇异值也有响应 的意义。
参考文献
1 https://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html
2 https://www.zhihu.com/question/22237507 3 We Recommend a Singular Value Decomposition（Feature Column from the AMS）