PCA 和 SVD
协方差矩阵
在上一篇 最小二乘法 的末尾提到了协方差矩阵以及用它来拟合,这里先再次回顾。
我们来观察一下:
假设有一堆点
,如果我们想要看这堆点的分散程度,一个办法是我们找出过质心 的直线 l = m + tv, 我们把点投影在直线l上,这些点的投影 就可以展示出来点在这个方法的分散程度。在不同的方向上点的投影的分散程度是不一样的,比如如果点的分布与直线比较一致的话,那么投影下来的点也会很分散,另一种情况就是点的分布和直线刚好垂直,这样点就会分得不是很开。
我们可以用式子表示出来投影的点在直线上的方差:
点在直线上的投影:
代回 var(l):
其中
, 这个矩阵又叫做 散布矩阵(scatter matrix).
S也就是协方差矩阵C的 n 倍:
,所以其实协方差矩阵也可以用来很好的展示点的分散程度。有了这个结论,我们先来看 PCA.
PCA Principal component analysis - 主成分分析
PCA 是很重要的概念,不仅在 CG 中, 在 ML 中也有它的一席之地。正如 PCA 的名称一样, PCA做的事情是如果给我们一堆数据,它可以帮我们分析出最主要的部分。
如果给我们一堆 2d 的点, PCA 可以帮我们找出距离这些点最近的直线,比如下图的 x' 轴。
如果给我们一堆 3d 的点, PCA 可以帮我们找出最能代表这些点的平面:
PCA 的很大一个用途是可以帮我们找 bounding box,这样可以做一些快速的相交测试,毕竟 ray-box-intersect 应该比 ray-object-intersect 简单许多。 而 PCA 可以给我们最紧密的 bounding box,比如下图:
PCA 当然还有许多其它的用途。
有第一部分的结论:
散布矩阵 可以用来很好的展示点的分散程度.
因为
, 所以S是一个对称矩阵,所以 S 可以写成: , 其中 当然就是特征矩阵,如果我们将特征值排序: ,那么对应的特征向量, 就是最主要的成分。
上述过程就是求 PCA 的过程:
算出质心 : 求 : 散布矩阵 : 其中 Y 的列为 特征分解 : 特征值排序 : 特征向量排序 : 取出我们需要的部分
看下图例子:
左边,点是没有一个特别的分布方向的,得到的散布矩阵会像这样:
会跟 非常接近。
右边,点有一个主要的分布方向,得到的散布矩阵会像这样:
就会十分接近与0.
PCA 的另一个常见的用途, CG 或者 ML 中,那就是降维。也就像最上面举的例子,2d 变直线, 3d 变平面, 比如在 ML 中,我们的特征维度太多了,那么我们当然就可以做 PCA, 找出我们想要的‘主要成分’。
PCA的一些计算技巧
如果 A 为 mxn 矩阵, m >> n, 假设 m = 16k, n = 100, 那么
的维度为 16k x 16k, 如果我们来计算这个矩阵的特征值,特征向量会需要巨大的计算量。
另一方面:
的维度为 100 x 100, 如果我们已经有了 的特征值和特征向量,那么 ,式子两边同时乘以 A,有:
所以
的特征向量可以通过 计算 的特征向量,再乘以A得到,这个技巧在A的维度相差很大的时候会很有用。
SVD Singular value decomposition - 奇异值分解
第一次听到 ‘奇异值分解’ 也是觉得这个名字怪神秘的。其实一点也不神秘,奇异值分解就是对我们一般的 mxn 矩阵 A,我们可以把它分解成:
正交矩阵 x 对角矩阵 x 正交矩阵, 其中对角矩阵 Σ,上的对角线值
就叫做奇异值。
方形的矩阵奇异值分解:
长方形矩阵可以有两种分解方式:
下面这种要在对角阵中填一些0:
所有 3x3 矩阵可以分解成 旋转,缩放,旋转就是因为SVD:
SVD 的用途非常广泛。
求
已知
, 那么 :
所以 Ax=b 也可以立刻解出来了。
rank (A)
rank A 当然也就可以立即求出来了。
PCA
如果我们有了 Y矩阵 (Y 的列为
) 的SVD,也就是 , 那么散布矩阵 可以简化成:
首先,V 是旋转矩阵, 本身正交:
, 齐次, 是对角矩阵,其矩阵相乘结果也是对角矩阵,那么也就对应 PCA 中的 , 所以 U 的列向量也就是与特征向量对应的主成分。很有意思的结论。
形状变换
SVD 的另一运用,比如我们有以下形状,我们想通过旋转和位移,让独角兽尽量的靠近成狮子。当然它们比较对齐的时候,我们当然就是希望标注的点之间的距离尽量变小,也就是右图中我们连接红色和灰色的点所得到的距离尽量最小。
狮子 : 独角兽 :
假设旋转矩阵为 R, 位移为 t,那么我们需要最小化的是:
首先我们需要让它们的质心在同一位置,也就是:
也就是:
其次我们展开:
令
,我们需要最小化的是:
其中:
是一个标量,因为 是 1xd, R 是 dxd, 是 dx1,然后对于任何标量,我们有 , 所以:
所以:
其中
是固定的,所以我们最小化上式,也就是最大化:
也就是我们需要最大化:
观察矩阵:
可得:
也就是我们需要最大化矩阵
的迹。
矩阵的迹有性质 tr(AB) = tr(BA), 所以:
是固定的,那么我们需要找到的就是一个R来最大化 ,假设我们有 ,我们将 S 奇异值分解
V,R,U都是正交矩阵,所以
也是正交阵,所以 M 的列向量满足: :
而
又是对角阵,所以:
所以当
均为1时迹最大,也就是 M = I,那么我们可以知道:
参考:
- <PCA and SVD> by Olga Sorkine-Hornung