奇异值分解

奇异值分解将线性代数中的很多概念串联起来了, 包括了四个子空间, 特征值, 特征向量, 正交矩阵, 对称矩阵等等。

初窥

根据线性变换的定义, 当一个矩阵M与一个向量相乘的时候, 相当于矩阵对向量在空间做了一个线性变换(伸缩或者改变角度)。 
考虑如下的关系

左边的矩阵相当于对一个点(x,y) 横坐标伸展了三倍, 纵坐标不变。

再考虑如下

在空间中的关系将变得不那么明朗, 当时如果将坐标轴旋转45度, 可以看出其仍是在一个方向上伸展了3倍。 为什么是45度呢, 因为矩阵的特征向量分别是

根据特征向量的定义, 矩阵M作用于特征向量后方向不变, 故我们仍看到是展缩的例子, 之所以是一个方向不变, 另外一个方向扩大了3倍, 是因为矩阵M的特征值分别是λ1=1,λ2=3, 故之。

然而上面的矩阵有些特殊, 第一个矩阵是对角矩阵, 第二个矩阵是对称矩阵, 都满足了特征值正交的特点。 对于任意的矩阵, 我们希望找到正交的特征向量, 满足如下的关系

考虑矩阵

如果足够仔细, 当坐标旋转58.28度的时候, 可以满足正交的关系。

可见, 不是所有的矩阵的特征向量都能正交。 因而, 我们的问题变为, 找到输入的正交向量v1,v2, 当矩阵M作用于其上的时候, 输出也为正交向量u1,u2, 其伸缩的大小由奇异值σ1,σ2决定。 因而有

对于一个普通的向量, 将其投影到v1,v2上, 即

通常写为矩阵的形式

U就是左奇异向量u1,u2构成的矩阵, ∑是奇异值σ1,σ2构成的对角矩阵, VT是右奇异向量v1,v2构成的矩阵的转置。

几何意义

一个直观的几何解释是用单位圆上的点来解释。 
假设矩阵M 的分解为

u1,u2,v1,v2是二维平面上的向量, 根据奇异值分解的性质,u1, u2线性无关,v1, v2线性无关。那么对二维平面上任意的向量x,都可以表示为:x=ξ1v1+ξ2v
当A作用在x上时,

η1=3ξ1, η2=ξ2,我们可以得出结论:如果x是在单位圆ξ21+ξ22=1上,那么y正好在椭圆η21/32+η22/12=1上。这表明:矩阵A将二维平面中单位圆变换成椭圆,而两个奇异值正好是椭圆的两个半轴长,长轴所在的直线是span{u1},短轴所在的直线是span{u2}.

上述的过程可以总结为

对于y=Ax, 用V^T旋转, 奇异值σ展缩,(如果m>n, 有一个zero-pad的效果, 如果m<n, 则有一个truncate的效果, 然后再经过U进行旋转。

因此, 奇异值分解的几何含义为:对于任何的一个矩阵,我们要找到一组两两正交单位向量序列,使得矩阵作用在此向量序列上后得到新的向量序列保持两两正交。奇异值的几何含义为:这组变换后的新的向量序列的长度。

如何计算

如何计算SVD中的所有元素呢, 回顾一下

一个直观的方法就是去除U或者V之一, 而专注其中一个,

由于A^TA自动满足是对称矩阵, 因此其特征值是正交的,上式相当于A=QQ^T 因此求ATA的特征向量, 特征值即可。 
同样的,

以Matlab为例, 计算一个奇异值分解的例子。

通过matlab的svd命令可以得到

证明

从我们的计算可以反过来验证Av_i=σ_i u_i是正确的。

应用

数据压缩

z该图为25x15的矩阵, 但其实主要是由三个元素构成, 如下图

通过SVD分析, 只有三个非零的奇异值。σ1=14.72,σ2=5.22,σ3=3.31 
因此, 该矩阵可表达为

我们只需要3x(15+25) + 3=123个数字就可以记录这个矩阵的信息了。

数据分析去噪

有两个非零的奇异值σ1=6.04,σ2=0.22, 第二个奇异值非常小, 可认为其对应的是噪声, 因此只选取第一个奇异值。

可以看出来, 噪声去除了。

网页排名

通常网页有两个评分属性, 一个是authority, 另外一个是hub; 记a(.)是从hub流进authority的评分, h(.)则是从authority流进hub的评分, 即

一个排名高的authority网页一定被评分高的hub网页链接, 而一个hub网页链接到一个authority高的网页的话其评分一定高, 如链接到amazon.com的网站的评分一定比链接到不知名的网站的评分高。

以向量的形式记录所有网站的两个评分ha,矩阵A记录网站的链接关系, 若网站p链接到网站q, 则矩阵中的元素为1, 否则为0. 从A的行来看, 记录了网页被其它网页链接的情况; 从列来看, 记录了网页链接到其它网页的情况, 则

注意到上面的式子存在以来的关系, 互相代入有

显然, 上面的方程都是关于矩阵的特征值, 通过引入特征值去掉←

因此我们的两个评分变成计算AA^T和A^TA的特征向量。 通过选取特征值较大的特征向量来构成最终的评分。

Reference:
[1]https://www.zhihu.com/question/22237507 
[2]http://www.ams.org/samplings/feature-column/fcarc-svd 
[3]Strang G, et al. Introduction to linear algebra[M]. Wellesley, MA: Wellesley-Cambridge Press, 1993.
[4]http://ee263.stanford.edu/lectures/svd-v2.pdf
[5]Manning C D, Raghavan P, Schütze H. Introduction to information retrieval[M]. Cambridge: Cambridge university press, 2008.