走进奇异值分解

本文译自 外网,且参考个别博文,旨在强化理解以及日后使用~

Introduction

奇异值分解(singular value decomposition)是理工科类的一项重要且基础的组成部分,对科研及实际成产活动都产生了巨大的影响。但是真正理解通透还是需要花点精力去捋一捋各个细节。

有时候我们只对 matrix 中的部分特征感兴趣,这时奇异值分解就为我们分析 matrix 提供了一个便利的方式(可以结合求解特征值,特征向量来理解)。本文就从几何角度形象生动地展开,并给出一些实际应用场景加深理解。

矩阵线性变换的几何意义

我们用 2*2 的对角矩阵示范:

在几何层面上,我们可以将这样的矩阵想象为将平面上一个点(x,y)转换为另一个点的转换矩阵:

该矩阵的几何意义就是将点(x,y)在 x 轴上拉伸 3 倍,y 轴上拉伸 1 倍(即不变)。图形化效果如下:

再看个例子:

转换前后如下图所示:

进一步旋转网格 45° 看看:

画风突然有些诡异了。为啥这个转换跟第一个对角矩阵的转换效果一样了?(都是在某一个方向上拉伸 3 倍)

这种特殊情况源自一个事实:转换矩阵 M 是对称矩阵

从数学的角度分析,给定一个对称矩阵 M,我们可以找到一组正交向量 Vi 以及对应的标量 λi 使得:Mvi = λivi

几何意义上讲,当乘以转换矩阵 M 时,其实就是对 Vi 进行拉伸变换。因为这个特性,我们把 Vi 称为矩阵 M 的特征向量, λi 称为 M 的特征值。(线代可证:不同特征值对应的特征向量正交

如果基坐标根据一个对称矩阵的特征向量对齐,那么该矩阵对基坐标空间的拉伸效果与特征向量的拉伸效果一样。

以上的例子只涉及一个方向的拉伸变换。接下来我们引入一个更通用的例子来证明:是否存在一个变换之后仍然正交的正交空间/grid。取非对称矩阵如下:


该矩阵可以产生几何中称为 shear 的效果.

沿着水平方向可以求出一族特征向量。但是这不是我们的目的,因为上图并未实现一个正交基坐标空间到另一个正交基坐标空间的转换。下面我们试着将第一个坐标空间顺时针旋转 30 °:

请注意,右侧红色平行四边形旋转的角度变大了。我们接下来将网格旋转60度。

现在看起来右边的网格几乎是正交的。事实上,将网格中的网格旋转大约 58.28 度的角度,才能实现正交。

奇异值分解

上文从纯集合的角度证明了:对于任意方阵,我们可以将其正交基坐标空间转移到另一个正交空间。下面我们用向量来解释这一事实:通过选择恰当的正交向量 V1V2,矢量 M*V1 和 M*V2 也可以是正交的。

我们将使用 u1u2 来表示 M*V1M*V2 方向的单位向量。 M*V1 和 M*V2 的模长由 σ1σ2 表示 – 描述了坐标空间在那些特定方向上拉伸的量,也称作为矩阵 M奇异值

由此可得:

又因为 V1V2 是正交单位向量(由旋转前可知),我们有:

上式两端左乘 M,可得:

单位向量点乘一个向量得到一个标量,因此右边的 M 可移到中间

且点乘可以转化为转置向量的叉乘:

进而可得:

简写:

其中 U 是由列向量 u1 和 u2 组成的矩阵,Σ 是对角矩阵,其实例是 σ1 和 σ2,V 是以 v1 和 v2 为列向量构成的矩阵。矩阵 V 上的上标 T 表示 V 的矩阵转置。

这就表明任意的矩阵 M 是可以分解成三个矩阵的乘积。表示了原始域的标准正交基,表示经过 M 变换后的转换域的标准正交基,Σ 表示了 中的向量与 中相对应向量之间的关系(伸缩比例)。

如何发现奇异值分解

任意矩阵皆可进行奇异值分解。我们还以上例展开说明(在图中可视化一个单位圆辅助理解),这个圆随着基坐标空间的变化也变成一个椭圆了。长轴和短轴重新定义了新的坐标空间。

请注意,长轴和短轴由 Mv1 和 Mv2 定义。因此,这俩矢量是单位圆上最长和最短的矢量。

换句话说,函数|Mx|在单位圆上的最大值在 x 取 V1 时最大,取 V2 时最小。这将问题简化为相当标准的微积分问题:我们希望优化单位圆上的函数值。事实证明,该函数的关键点出现在矩阵 MT的特征向量处。由于 MT是对称的,不同特征值对应的特征向量是正交的。如此就得到了两两正交的特征向量族。

然后奇异值就等于 σi = |Mvi|, 可以在 Mv方向上得到单位向量 ui,但是,为什么u两两正交?

解:假设 σi and σj 是俩不同(且不为 0)的奇异值。有,

因为MT是对称的,不同特征值对应的特征向量 vi是正交的,进一步可得,

故,ui and u是正交的。所以我们证明了:一组正交向量 vi 可以转换到另一组正交向量 ui. 奇异值描述了在不同方向上拉伸的程度。

实际上,人们通常不会这样进行奇异值分解,因为这样很低效。

another example

假定有奇异矩阵

该矩阵的可视化效果如下:

这个例子中的第二个奇异值是 0,所以,

也就表明,奇异值为 0 的对应向量不参与 M 的奇异值分解。同时可以看到, M 的秩等于转化后的方向向量的个数(也就是非 0 奇异值的个数)

数据压缩

奇异值分解可以高效地表示数据。假设我们打算发送一张 15*25 大小的黑白图片:

由于该图只有三种列向量(下图所示),所以应该有更高效的表示方法。

我们现在把图片量化为矩阵形式:

对以上矩阵 M 进行奇异值分解,你会得到以下三个非 0 奇异值:

所以矩阵 M 可以表示为:

这意味着我们得到三个向量 vi,每个包含 15 个元素,三个向量 ui,每个包含 25 个元素,以及三个奇异值 σi这就表示我们可以仅用 123 =((15+25+1)*3)个数来表示,而不是 375 = (15*25) 个数。

为毛这里只有三个非 0 的奇异值?

请记住,非零奇异值的数量等于矩阵的秩。在本例中,我们看到矩阵中只有三个线性独立(线性无关)的列,这意味着秩为 3。

降噪

前面的例子展示了我们如何处理许多奇异值为零的情况。通常来说,大的奇异值指向我们感兴趣的地方。仍以上图为例,假设我们使用一个扫描仪将上图传输到电脑上,但是这一过程引入了一些噪点:

我们可以照旧对上图进行奇异值分解,我们得出:

显然,前面 3 个最重要,我们可以假设其它的奇异值都是噪声并取逼近结果:

近似图片如下:

数据分析

数据总是伴随着噪声:无论你多么小心谨慎。一定要记住:大的奇异值指向重要的特征,所以使用奇异值分解来研究数据就很自然了。

假如我们收集到如下数据:

我们可以把这些数据量化到矩阵中。

然后来个奇异值分解得到:

当一个奇异值比另一个大很多的时候,我们可以合理的假设  σ2  是噪音,它实际上应该为 0.这样的话,本例的矩阵的秩就等于 1 了。也就是说全部数据呈绝对的线性相关:

这个简短的例子实际上可以理解为主成分分析(PCA)的雏形,PCA 使用奇异值来检测数据中的依赖关系和冗余的技术。

以类似的方式,奇异值分解可用于检测数据中的分组,这解释了为什么奇异值分解被用于尝试改进 Netflix 的电影推荐系统。你观看过的电影评分允许某个节目将你归为一组评分与你相似的人中去。可以通过选择群组中其他人评价较高的电影来进行推荐。

Share this to:

发表评论

电子邮件地址不会被公开。 必填项已用*标注