从几何解释SVD分解

介绍

SVD分解(奇异值分解),实际上,SVD分解不但很直观,而且极其有用。SVD分解提供了一种方法将一个矩阵拆分成简单的,并且有意义的几块。它的几何解释可以看做将一个空间进行旋转,尺度拉伸,再旋转三步过程

基本理论

首先来看一个对角矩阵,

从几何解释SVD分解

几何上, 我们将一个矩阵理解为对于点 (x, y) 从一个平面到另一个平面的映射:

从几何解释SVD分解

图1所示,显示了这个映射的效果: 平面被横向拉伸了3倍,纵向没有变化。

从几何解释SVD分解

图1

对于另一个矩阵

从几何解释SVD分解

它的效果如图2(a)所示。图2(a)这样一个变化并不是很好描述,然而当我们将坐标系旋转45度后,我们可以看出.如图2(b)所示,这时,我们发现这个新的网格上发生的变化和网格在对角阵下发生变化的效果相似。

从几何解释SVD分解      从几何解释SVD分解

图2(a)                                                                                                                         图2(b)

这是一个对称矩阵的例子,可以看出,对称矩阵经过旋转后,其作用就和对角阵类似了。数学上,对于一个对称矩阵 M, 我们可以找到一组正交向量 vi 从而 Mvi 相当于 vi上的标量乘积; 也就是

Mvi = λivi
λi 是标量,也就是对应对角阵中对角线上的元素. 由于这个性质,我们称 vi M 的特征向量;  λi 为特征值. 一个对称矩阵不同特征值对应的特征向量是正交的。对于更广泛的情况,我们看看是否能从一个正交网格转换到另一个正交网格. 考虑一个非对称矩阵:
从几何解释SVD分解

这个矩阵的效果形象的称为剃刀(shear)如图3(a)所示。这个矩阵将网格在水平方向拉伸了,而垂直方向没有变化。如果我们将网格旋转大约60度左右,这两个网格就又会都变为正交的了,如图3(b)所示。

从几何解释SVD分解  从几何解释SVD分解

图3(a)                                                                                                        图3(b)

奇异值分解:考虑一个 2 *2 矩阵, 我们可以找到两组网格的对应关系。用向量表示,那就是当我们选择合适的单位正交向量v1v2,Mv1Mv2 也是正交的,如图4(a)所示.我们使用u1u2 代表 Mv1Mv2的方向. Mv1Mv2 的长度表示为 σ1 和 σ2,也就是网格在每个方向的拉伸. 这两个拉伸值叫做M的奇异值(sigular value),图4(b)所示

从几何解释SVD分解        从几何解释SVD分解

图4(a)                                                                                  图4(b)

和前面类似,我们可以有

Mv1 = σ1u1 和 Mv2 = σ2u2

我们一直讨论的 v1v2 是一对正交向量, 对于一般的向量x,我们有这样的投影关系

x = (v1从几何解释SVD分解x)v1 + (v2从几何解释SVD分解x)v2
也就是说
Mx = (v1从几何解释SVD分解x) Mv1 + (v2从几何解释SVD分解x) Mv2
Mx = (v1从几何解释SVD分解x) σ1u1 + (v2从几何解释SVD分解x) σ2u

即:Mx =u1σ1v1Tx +u2σ2v2Tx    --->    M = u1σ1v1T +u2σ2v2T

这个关系可以写成矩阵形式:  M = UΣVT

其中,U 的列是 u1u2, Σ  σ1 和 σ2构成的对角阵,  V 的列是v1v2.  即V描述了域中的一组正交基,U描述了相关域的另一组正交基,Σ 表述了U中的向量与V中向量的拉伸关系.

奇异值分解可以应用于任何矩阵,对于前面的例子,如果我们加上一个圆,那它会映射成一个椭圆,椭圆的长轴和短轴定义了新的域中的正交网格,可以被表示为Mv1 and Mv2如图5所示。

从几何解释SVD分解

图5

换句话说,单位圆上的函数 |Mx| 在  v1 取得最大值,在v2取得最小值. 这将单位圆上的函数优化问题简化了。可以证明,这个函数的极值点就出现在MTM的特征向量上,这个矩阵一定是对称的,所以不同特征值对应的特征向量vi是正交的.σi = |Mvi|就是奇异值, ui 是 Mvi方向的单位向量.

Mvi = σiui
Mvj = σjuj.
Mvi从几何解释SVD分解 Mvj =viTMT Mvj =vi从几何解释SVD分解 MTMvj = λjvi从几何解释SVD分解vj = 0.
即:        Mvi从几何解释SVD分解Mvj = σiσjui从几何解释SVD分解uj = 0

因此,uiuj 也是正交的。所以我们就把一组正交基vi 变换到了另一组正交基ui.

另一个例子我们来看一个奇异矩阵(秩为1,或只有一个非零奇异值)

 

从几何解释SVD分解

它的效果如下

从几何解释SVD分解

图6

在这个例子中,第二个奇异值为0,所以 M = u1σ1v1T. 也就是说,如果有奇异值为0,那么这个矩阵就有降维的效果。因为0奇异值对应的维度就不会出现在右边。这对于计算机科学中的数据压缩极其有用。例如我们想压缩下面的15x25 像素的黑白图像.我们可以看出这个图像中只有三种列,即

从几何解释SVD分解     从几何解释SVD分解从几何解释SVD分解从几何解释SVD分解  从几何解释SVD分解

图7(a)                     图7(b)                                          图7(c)

然而当我们做了奇异值分解,会发现非零奇异值仅有3个,

σ1 = 14.72, σ2 = 5.22, σ3 = 3.31
 因此,这个矩阵就可以被表示为   M=u1σ1v1T +u2σ2v2T +u3σ3v3T

也就是说我们用三个长度为15的向量vi,三个长度为25的向量ui,以及三个奇异值,总共123个数字表示了这个375个元素组成的矩阵。奇异值分解找到了矩阵中的冗余信息实现了降维。可以看出,奇异值分解捕获了图像中的主要信息。因此,又假设上一个例子里引入了噪声,当我们用同样的方法做奇异值分解,我们得到如下非零奇异值

σ1 = 14.15,σ2 = 4.67,σ3 = 3.00,σ4 = 0.21,σ5 = 0.19,...,σ15 = 0.05
显然,前三个奇异值比其他的大很多,说明其中包括了绝大部分信息。如果我们只要前三个,
M 从几何解释SVD分解u1σ1v1T +u2σ2v2T +u3σ3v3T

我们就实现了图像的降噪。

从几何解释SVD分解   从几何解释SVD分解

图8(a)噪声图像                              图8(b)降噪图像

(注:上述图像来自网络)

参考资料

[1]Hoggar,S.G.(2006),"Mathematics of Digital Images:Creation,Compression,Restoration,Recognition".


关于更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.



从几何解释SVD分解

上一篇:预约购票模式,完全杜绝网络黄牛、网络刷票,给每一个人一个公平的购票机会,释放12306的压力


下一篇:CareerCup Eliminate all ‘b’ and ‘ac’ in an array of characters