Python中的最小特征值

Question

我在想，numpy有没有高效的方法来计算对称矩阵的最大或最小特征值，如果能不进行完整的特征分解就更好了。

我发现以下模块可以实现特征分解：

1. scipy.linalg;
2. numpy linalg;
3. scipy sparse linalg。

scipy/sparse/linalg/eigsh可以输出前k个最小（或最大）特征值和特征向量； scipy/linalg/eigh也提供了选择特征值子集的选项； numpy/linalg/eigvalsh则输出所有的特征值。不过，如果我只想要某个特定的特征值，它们似乎都不是很高效。

我做了一些简单的测试，比较找到最大特征值所花的时间。 所有方法给出的结果都差不多，numpy.linalg中的特征分解函数似乎是最有效的，尽管它需要进行完整的谱分解。有没有更好的方法来完成这个任务呢？

以下是测试代码和结果

import numpy as np
import scipy.linalg
import scipy.sparse.linalg
import time


def test_scipy_eig(a):
    p = a.shape[0]
    w = scipy.linalg.eigh(a, eigvals=[p-1, p-1], eigvals_only=True)
    return w


def test_scipy_sparse_eig(a):
    p = a.shape[0]
    w = scipy.sparse.linalg.eigsh(a, k=1, which='LA', return_eigenvectors=False)
    return w


def test_numpy_eig(a):
    w = np.linalg.eigvalsh(a)
    return w


p = 2000
a = np.random.normal(0,1,(p,p))
b = a.dot(a.T)

start = time.time()
w1 = test_scipy_eig(b)
t1 = time.time() - start


start = time.time()
w2 = test_numpy_eig(b)
t2 = time.time() - start


start = time.time()
w3 = test_scipy_sparse_eig(b)
t3 = time.time() - start
print "time expense:\n scipy:%f  numpy:%f scipy_sparse:%f " % (t1, t2, t3)

print "largest eigenvalue:\n scipy:%f  numpy:%f scipy_sparse:%f " % (w1[0], w2[-1], w3[0])

输出

time expense:
 scipy:1.427211  numpy:1.395954 scipy_sparse:4.520002 
largest eigenvalue:
 scipy:7949.429984  numpy:7949.429984 scipy_sparse:7949.429984 

Answer 1

你的这个小问题实际上在用迭代方法找最大特征值时比较复杂，因为你有几个特征值聚集在最大特征值附近。

如果你把

a = np.random.normal(0,1,(p,p))

换成

a = np.random.rand(p, p)

那么你会发现使用scipy.sparse求解器的效果会大不相同。

你想要的答案是：使用哪种正确的方法取决于你手头的问题，不能仅仅通过小例子来决定，除非这个小例子的特征值、稀疏结构和大小与实际要解决的问题相似。