【线性代数】通俗的理解奇异值以及与特征值的区别,还有奇异值分解及其应用 | 您所在的位置:网站首页 › 分成和分解是一样吗 › 【线性代数】通俗的理解奇异值以及与特征值的区别,还有奇异值分解及其应用 |
奇异值分解,就是把矩阵分成多个“分力”。奇异值的大小,就是各个“分力”的大小。 之前在介绍矩阵特征值与特征向量的时候,也是以运动作为类比。 一、通俗理解奇异值1、翻绳 对于翻绳的这个花型而言,是由四只手完成的: 我们可以认为这个花型是由两个方向的力合成的: 容易想象,如果其中一个力(相比另外一个力而言)比较小的话,那么绳子的形状基本上由大的那个力来决定: 2、奇异值分解与奇异值 类比于翻绳,我们可以认为: 奇异值分解,就是把矩阵分成多个“分力”。 奇异值的大小,就是各个“分力”的大小。 2.1 奇异值分解几何解释 下面通过一个具体的矩阵例子来解释下,比如: 根据之前的类比,矩阵是“力”,“力”怎么画出来呢? 翻绳游戏中的“力”要通过绳子的形状来观察。很显然要观察矩阵也需要一个载体。 我们通过单位圆来观察矩阵: 把这个单位圆的每一点都通过 对 实际上,将 我们来看看第一个“分力”: 作用在单位圆这个“橡皮筋”上的效果: 可怜的“橡皮筋”被拉成了一根线段。 我们来看看第二个“分力”: 作用在单位圆这个“橡皮筋”上的效果: 可怜的“橡皮筋”被拉成了另外一根线段。 这两个“分力”一起作用的时候,可以想象(画面自行脑补),单位圆这个“橡皮筋”被拉成了椭圆: 这里再用一幅图来概括: 上面的几何解释其实已经比较清晰了,但正交这一点并没有很好的被体现出来。 以下继续重复解释一下,以加深印象。 以 上图的含义是,我们在左图首先选定了两个单位正交基向量 因此,对于上面左图中二维空间(正方形格子)的任意一个向量 (3)式左右同时乘以矩阵 (4)式结合(1)和(2): 将内积操作通过用转置表示出来: 两边同时消去X: 通常,我们将(7)式的形式写为: 从(8)式我们可以看到, 同时,还有另一种几何解释,与最开始讲的相同,也就是把SVD分解的过程看做是将单位圆的半径通过变换伸缩为椭圆的两个半轴。 如下图: 2.2 物理解释 个人理解,从信号的角度来讲,SVD过程的物理意义是将矩阵的能量集中到奇异值矩阵的左上角的过程。
例如,上图中的左图为随机生成的一幅256x256的图像,值都是在0-255之间。右图为左图SVD分解之后的奇异值矩阵,颜色越亮,代表了值越大,也就是能量越大。因此SVD的过程就是通过变换,将原空间的能量重新聚集分配,在新的空间集中的过程,这就是SVD的物理意义。通过这个物理意义,我们可以做许多的应用,例如数据的压缩,图像的滤波,以及推荐算法等,这些会在后文说到。 2.3 奇异值的大小 刚才举的矩阵的两个“分力”大小,只相差一倍,如果相差很大会怎么样? 换一个矩阵 这两个“分力”的奇异值相差就很大,大概相差了40倍。 单位圆被 我们试试,把小的那个奇异值去掉会怎么样:
这个直线和之前的椭圆看上去差不多。 回到之前的比喻,两个相差很大的分力作用在“橡皮筋”上,“橡皮筋”的形状可以说完全取决于大的那个分力。 奇异值分解实际上把矩阵的变换分为了三部分: 旋转 拉伸 投影(当有奇异值为0时以及非方阵) 拿刚才的: 举例子(方阵没有投影,不过不影响这里思考): 单位圆先被旋转,是没有形变的: 再进行拉伸,这里决定了单位圆的形状,奇异值分别是椭圆的长轴和短轴(奇异值如果为0,则相当于投影到某一个基向量上去): 最后,被旋转到最终的位置,这一过程也没有发生形变: 所以,奇异值决定了形变,大小决定在形变中的重要性。 二、奇异值与特征值、特征向量的联系与区别前一小节介绍了奇异值在矩阵变换中发挥的作用,会发现这和我们讲方阵的特征值与特征向量时特别相似。那两者到底有什么区别呢?接下来就细细介绍一下。 1 奇异值 之前没有详细讲奇异值分解,这里先来谈谈奇异值分解在数学上的定义。 特征值分解是一个提取矩阵特征很不错的方法,但是它只是对方阵而言的,在现实的世界中,我们看到的大部分矩阵都不是方阵,比如说有 假设 那么奇异值和特征值是怎么对应起来的呢?首先,我们计算得到 这里得到的 这里的
右边的三个矩阵相乘的结果将会是一个接近于 2 奇异值与特征值有什么相似之处与区别之处 其实从之前奇异值的几何解释以及奇异值的数学定义都可以看出奇异值和特征值是两个相当接近的概念。奇异值的优点在于其不受限于原始矩阵 矩阵可以认为是一种线性变换,如果将这种线性变换放在几何意义上,则它的作用效果和基的选择有关。(基是理解很多知识点的重中之重)。 以 比如说: 其几何意义为在水平 奇异值分解正是对线性变换这三种效应的一个析构。 而特征值分解其实是对旋转缩放两种效应的归并。有投影效应的矩阵不是方阵或者是奇异方阵,必有特征值为0。特征向量由 总而言之,特征值分解和奇异值分解都是给一个矩阵(线性变换)找一组特殊的基,特征值分解找到了特征向量这组基,在这组基下该线性变换只有缩放效果。而奇异值分解则是找到另一组基,这组基下线性变换的旋转、缩放、投影三种功能独立地展示出来了。 又因为有投影效应的矩阵不是方阵或者是奇异方阵,没有特征值或特征值为0,所以奇异值分解可以适用于所有矩阵,但特征值分解就仅仅适用于可逆方阵了。 另一方面,将矩阵变换析构出来方便于直观地理解矩阵变换的各个部分。特征值分解出来的矩阵有时并不直观,多个旋转变换冗杂在一起以及特征值会出现复数等情况。 三、SVD分解的应用SVD在实际中应用非常广泛,每个应用场景再单写一篇文章都没有问题。这里我们先不做过多的展开,先举两个最重要的方面。 1 降维 通过上面的式子很容易看出,原来矩阵的特征有维。而经过SVD分解之后,完全可以用前个非零奇异值对应的奇异向量表示矩阵的主要特征。这样,就天然起到了降维的作用。 2 压缩 还是看上面的式子,再结合第三部分的图,也很容易看出,经过SVD分解以后,要表示原来的大矩阵,我们只需要存三个较小的矩阵的即可。而这三个较小矩阵的规模,加起来也远远小于原有矩阵。这样,就天然起到了压缩的作用。 四、奇异值的计算:奇异值的计算是一个难题,是一个O(N^3)的算法。在单机的情况下当然是没问题的,matlab在一秒钟内就可以算出1000 * 1000的矩阵的所有奇异值,但是当矩阵的规模增长的时候,计算的复杂度呈3次方增长,就需要并行计算参与了。Google的吴军老师在数学之美系列谈到SVD的时候,说起Google实现了SVD的并行化算法,说这是对人类的一个贡献,但是也没有给出具体的计算规模,也没有给出太多有价值的信息。 其实SVD还是可以用并行的方式去实现的,在解大规模的矩阵的时候,一般使用迭代的方法,当矩阵的规模很大(比如说上亿)的时候,迭代的次数也可能会上亿次,如果使用Map-Reduce框架去解,则每次Map-Reduce完成的时候,都会涉及到写文件、读文件的操作。个人猜测Google云计算体系中除了Map-Reduce以外应该还有类似于MPI的计算模型,也就是节点之间是保持通信,数据是常驻在内存中的,这种计算模型比Map-Reduce在解决迭代次数非常多的时候,要快了很多倍。 Lanczos迭代就是一种解对称方阵部分特征值的方法(之前谈到了,解 由于奇异值的计算是一个很枯燥,纯数学的过程,而且前人的研究成果(论文中)几乎已经把整个程序的流程图给出来了。更多的关于奇异值计算的部分,将在后面的参考文献中给出,这里不再深入,我还是focus在奇异值的应用中去。 五、SVD与广义逆矩阵在认识矩阵的广义逆之前,先来回顾一下方阵的逆。 对于一个 那么对于非方阵来说情况又是怎样的? 比如对于 矩阵的广义逆由Moore在1920年提出,后来在1955年经过Penrose发展得到如下定义: 对任意 则称 由于M-P的四个方程都各有一定的解释,并且应用起来各有方便之处,所以出于不同的目的,常常考虑满足部分方程的 弱逆,弱逆不唯一。为了引用方便,下面给出广义逆矩阵的定义: 对于 实际上有结论:如果 不唯一。也就是说一个矩阵
那么,不难验证 有了广义逆矩阵 秩是 的也就是这个解。 六、SVD与最小二乘法最常见的最小二乘问题是线性最小二乘问题。比如在三维空间有如下四个点 现在用一个方程 那么,进一步得到: 接下来用一个定理求最小二乘解,定理内容如下: 如上述超定系数方程组,一般情况下它是没有解的,但是我们可以让 这样最小二乘解又变成了解线性方程组问题,可以先用SVD来求出广义逆矩阵,然后解出 注:其实很容易发现这就是之前介绍的Normal Equation方法,这里主要介绍了广义逆可以通过SVD分解来求解得到。
参考文章: 如何通俗地理解奇异值? 机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用 矩阵分解 SVD分解 奇异值矩阵分解(Singular Value Decomposition)的一些感想这篇文章没有引到,但看起来还不错,值得一看。 最近又看到一篇写的不错的文章,下次将会继续补充。 |
CopyRight 2018-2019 实验室设备网 版权所有 |