介绍
SVD分解(奇异值分解),实际上,SVD分解不但很直观,而且极其有用。SVD分解提供了一种方法将一个矩阵拆分成简单的,并且有意义的几块。它的几何解释可以看做将一个空间进行旋转,尺度拉伸,再旋转三步过程。
基本理论
首先来看一个对角矩阵,
几何上, 我们将一个矩阵理解为对于点 (x, y) 从一个平面到另一个平面的映射:
图1所示,显示了这个映射的效果: 平面被横向拉伸了3倍,纵向没有变化。
图1
对于另一个矩阵
它的效果如图2(a)所示。图2(a)这样一个变化并不是很好描述,然而当我们将坐标系旋转45度后,我们可以看出.如图2(b)所示,这时,我们发现这个新的网格上发生的变化和网格在对角阵下发生变化的效果相似。
图2(a) 图2(b)
这是一个对称矩阵的例子,可以看出,对称矩阵经过旋转后,其作用就和对角阵类似了。数学上,对于一个对称矩阵 M, 我们可以找到一组正交向量 vi 从而 Mvi 相当于 vi上的标量乘积; 也就是
这个矩阵的效果形象的称为剃刀(shear)如图3(a)所示。这个矩阵将网格在水平方向拉伸了,而垂直方向没有变化。如果我们将网格旋转大约60度左右,这两个网格就又会都变为正交的了,如图3(b)所示。
图3(a) 图3(b)
奇异值分解:考虑一个 2 *2 矩阵, 我们可以找到两组网格的对应关系。用向量表示,那就是当我们选择合适的单位正交向量v1 和v2,Mv1 和Mv2 也是正交的,如图4(a)所示.我们使用u1 和 u2 代表 Mv1 和Mv2的方向. Mv1 和Mv2 的长度表示为 σ1 和 σ2,也就是网格在每个方向的拉伸. 这两个拉伸值叫做M的奇异值(sigular value),图4(b)所示。
图4(a) 图4(b)
和前面类似,我们可以有
Mv1 = σ1u1 和 Mv2 = σ2u2
我们一直讨论的 v1 和v2 是一对正交向量, 对于一般的向量x,我们有这样的投影关系
Mx = (v1x) σ1u1 + (v2x) σ2u
即:Mx =u1σ1v1Tx +u2σ2v2Tx ---> M = u1σ1v1T +u2σ2v2T
这个关系可以写成矩阵形式: M = UΣVT
其中,U 的列是 u1 和u2, Σ σ1 和 σ2构成的对角阵, V 的列是v1 和v2. 即V描述了域中的一组正交基,U描述了相关域的另一组正交基,Σ 表述了U中的向量与V中向量的拉伸关系.
奇异值分解可以应用于任何矩阵,对于前面的例子,如果我们加上一个圆,那它会映射成一个椭圆,椭圆的长轴和短轴定义了新的域中的正交网格,可以被表示为Mv1 and Mv2。如图5所示。图5
换句话说,单位圆上的函数 |Mx| 在 v1 取得最大值,在v2取得最小值. 这将单位圆上的函数优化问题简化了。可以证明,这个函数的极值点就出现在MTM的特征向量上,这个矩阵一定是对称的,所以不同特征值对应的特征向量vi是正交的.σi = |Mvi|就是奇异值, ui 是 Mvi方向的单位向量.
因此,ui 和uj 也是正交的。所以我们就把一组正交基vi 变换到了另一组正交基ui.
另一个例子,我们来看一个奇异矩阵(秩为1,或只有一个非零奇异值)
它的效果如下
图6
在这个例子中,第二个奇异值为0,所以 M = u1σ1v1T. 也就是说,如果有奇异值为0,那么这个矩阵就有降维的效果。因为0奇异值对应的维度就不会出现在右边。这对于计算机科学中的数据压缩极其有用。例如我们想压缩下面的15x25 像素的黑白图像.我们可以看出这个图像中只有三种列,即
图7(a) 图7(b) 图7(c)
然而当我们做了奇异值分解,会发现非零奇异值仅有3个,
也就是说我们用三个长度为15的向量vi,三个长度为25的向量ui,以及三个奇异值,总共123个数字表示了这个375个元素组成的矩阵。奇异值分解找到了矩阵中的冗余信息实现了降维。可以看出,奇异值分解捕获了图像中的主要信息。因此,又假设上一个例子里引入了噪声,当我们用同样的方法做奇异值分解,我们得到如下非零奇异值
我们就实现了图像的降噪。
图8(a)噪声图像 图8(b)降噪图像
(注:上述图像来自网络)
参考资料
[1]Hoggar,S.G.(2006),"Mathematics of Digital Images:Creation,Compression,Restoration,Recognition".
关于更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.