Categories

Calendar

November 2017
M T W T F S S
« Jun    
 12345
6789101112
13141516171819
20212223242526
27282930  

求最小的几个特征值

在机器学习中经常都会遇到特征值问题,例如 Laplacian Eigenmaps 或者一大堆的 KernelPCA 派的降维方法,或者谱聚类之类的。通常都是对于一个很大并且比较稀疏的矩阵,求最大或者最小的几个特征值以及对应的特征向量。在 Matlab 里,eig 函数可以用来求得一个矩阵的全部特征值和特征向量,然而,如果我们只需要其中最大或者最小的那几个,用 eig 来求就显得杀鸡用牛刀了,费力还不讨好。而且,eig 还不能处理稀疏矩阵的情况,所以,这个时候通常就需要 eigs 出场了。

eigs 可以只求矩阵的几个最小的或者最大的(或者最接近某一个数值的)特征值和对应的特征向量,并且能够处理稀疏矩阵(如果矩阵规模很大而且稀疏程度有很高的话,使用稀疏矩阵速度会快很多)。当然它使用的算法和 eig 不一样,是迭代的方式(具体的细节我也不是很清楚,记得数值分析课上讲过 power method ,不过也忘得精光了 -.-)。这也造成了一个小缺点,就是当矩阵是 singular 或者 near-singular 的时候,如果求最小的几个特征值,就会有问题。例如下面这个极端的例子,我们造一个 rank 为 1 的矩阵:

a = rand(3,1);
A = a*a';
eigs(A, 2, 'SM');

Matlab 就会在这里出错。让人很痛苦,因为有时候会在数据中碰到矩阵 near-singular 的情况。一开始我找不到解决办法,因为 eig 是可以处理 singular 矩阵的,所以干脆在遇到 eigs 出错的时候转由 eig 来计算,然后手工选出最小的几个特征值和特征向量。

不过这样子显然低效很多,特别是在矩阵维度是几千而需要的特征值特征向量就是几个的时候。当然,这个时候我可以这样子:

不过最后有一天我突然想到了其实这个问题似乎很简单。关于特征值和特征向量,是这个样子的:

\[
A\mathbf{v} = \lambda \mathbf{v}
\]

如果矩阵 $A$ 是 singular 的话,那么我加上一个单位矩阵 $I$ 好了:

\[
(I + A)\mathbf{v} = \mathbf{v} + A\mathbf{v} = (1+\lambda)\mathbf{v}
\]

也就是说,加上一个单位阵再求特征值问题的话,得出来的特征向量和原来 $A$ 的特征向量是一样的,对应的特征值也只是多了一个增量 1 而已。另一方面,加上了单位阵之后就不再 singular 了,所以 eigs 也可以用了。 :)

ps: 当然,何时选用 eig 还是 eigs 还是要依赖于计算机性能、经验、心情等一些各种因素的,比如,其实 eig 算 $100\times 100$ 的矩阵的全部特征值和特征向量还是非常迅速的——几乎是瞬间完成。

20 comments to 求最小的几个特征值

  • rongekuta

    非常好的建议!
    我遇到类似的问题,即当矩阵的条件数过大(病态),容易造成MATLAB特征值分解的误差,产生复数的现象,在遇到这种问题时,可以也对对角线元素进行修正,其实也就是加上一个单位矩阵

  • Tiansheng

    有一个很坑爹的事情是, 如果用svds, 不传那个 # of eigs的话… 他只会算前6个

    唉唉.. 上次完全没有发现, winsty哥哥帮我找了好一会

  • Tiansheng

    对啊.. 我觉得这个很奇怪耐…
    按照常理能算全部不是很好喵~~

    • 没有呀,全部算的话,只要用 svd/eig 就可以了,速度快精度高。svds/eigs 是用的迭代法,专门用在只需要算少数几个特征值的时候的。有时候矩阵维度太高了用 svd/eig 算不了,但是如果只需要少数的几个 eigen pair 的话,svds/eigs 就是极佳的选择了。一般都不会用 svds/eigs 去算全部特征值的。 :)

  • Tiansheng

    恩恩~ 是的~~

  • kaka2222

    话说我用eigs去计算某归一化拉氏矩阵的几个最小特征值,怎么经常算出不同的结果额,虽然它们都很接近于0,对应的特征向量更是多变。我的稀疏矩阵转成满矩阵大概是6W*6W的规模。另,你说的singular是什么意思啊?svds/eigs 怎么用?

    • singular 就是“奇异”的意思,奇异或者接近奇异的情况会导致迭代法数值解不稳定甚至是失败。你可以尝试一下加上一个 speye ,然后再将算出来的特征值减 1 。

  • kaka2222

    那奇异的时候MATLAB本身是不会报错的是吧?我的解不稳定了就基本可以判定为矩阵奇异了?但是在没有奇异的时候,为什么对应的特征向量会有微妙的变化呢?

  • Zhiquan

    如果一个矩阵是A = [-1 0; 0 0]; A + I = [0 0; 0 1]还是奇异矩阵。
    这个怎么办?

  • Springer

    呵呵,佩服楼主的认真精神,漫画很棒!

    不过这个特征值平移的方法似乎在学数值分析的时候就应该能想到吧,嘻嘻嘻

    ._.bb

  • shen

    你好,看了你的“求最小的几个特征值”文章,深受启发!
    想问你一个有关特征分解的问题。对于LDA(线性鉴别分析)而言,最后求得是一个广义特征方程问题,可以通过eig(inv(Sw)*Sb)来进行求解或者eig(Sb, Sw)也可以,但是两者的结果是有差别的,特别是用前者的话,会出现特征值、特征向量为复数的形式,而且最后用它投影做分类会有影响,如果接着用matlab中的knnclassify进行分类的话,还有可能出错;而用后者则不会。
    我想问怎么去避免这样的问题?如果遇到复特征向量能否直接把虚部去掉吗?
    更一般的问题,并且如果遇到非对称的方阵,怎样才能避免不出现复特征向量。

    打扰到您,非常抱歉!

    • 你好,matlab 求特征值问题的时候好像可以指定复数还是实数问题的,不太记得 eig 还是 eigs 其中好像至少有一个是类似的选项的,你仔细看看帮助文档下?

  • yuz

    写的很好,点赞!
    求eig的时候为了防止得到的结果near-singular加一个单位矩阵的方法似乎是经典的方法,在LLE的实现代码就有用到,他是加了一个1e-3 * eye(n)的 对角矩阵,和你这个是一个意思

Leave a Reply

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>