我们能否仅计算一个非常大的稀疏矩阵的第n个特征值和特征向量？

Question

我有一个非常庞大的稀疏矩阵A，大小为7Mi-by-7Mi。我正在使用Matlab的eigs(A,k)函数，该函数可以计算前k个特征向量和特征值。我需要获取所有的特征向量和特征值，但是我无法存储所有特征向量，因为它需要大量的内存。

是否有任何方法（在Matlab或Python中），可以通过for循环逐个获取特征向量？即在第ith次迭代中，我可以获得第ith个特征向量和特征值。

- Luqman Saleem

---

大多数计算特征值/特征向量的算法都是从最大特征值到最小特征值进行计算的；MATLAB的'eigs()' 算法肯定是这样的。你需要找到一种不依赖于先前计算的特征值的算法，然后进行循环计算。（或者当然可以购买更多的 RAM）。另外，需要计算7M个特征值可能会引起 XY 问题 ，如果您告诉我们您需要它们来做什么，我们可能会告诉您根本不需要这些特征值，而是需要其他的解决方案。 - Adriaan

@Adriaan 在 eigs.m 文件中，似乎使用的算法是 Krylov-Schur。计算下一个特征值是否真的需要所有先前计算出的特征值，还是只需要一些？如果不需要，那么可能可以做到这里所要求的。 - Trilarion

我认为这是不可能的。特征值依赖于整个矩阵，你需要整个矩阵来计算每一个特征值。如果你裁剪一行，特征值就会改变。 - Ander Biguri

你看过 numpy.linalg.eig() 吗？也许你可以在问题中添加为什么这不是一个有前途的方法（问题应该始终包含关于已经尝试过的事情以及它们失败的原因的信息）。 - Alfe

我猜这里的诀窍在于原始的稀疏矩阵之所以适合放入内存，是因为它非常稀疏。也许计算特征向量的所有中间步骤都只产生非常稀疏的矩阵，因此，如果您使算法使用相同的稀疏矩阵类型，则可以在内存中计算出所有特征向量？ - Alfe

一些算法通过移位从最小到最大进行工作；而另一些则从最大到最小。明智地选择。 - duffymo

Answer 1

如果您对所寻找的特征值有一个较好的猜测，比如lambda_guess，您可以在上面使用Power iteration。

(A - lambda_guess* Id)^-1

这种方法有时被称为反移位法。在这里，该方法将收敛于最接近lambda_guess的特征值（您的猜测越好，收敛速度越快）。请注意，您不需要存储逆矩阵，而只需计算解： x_next_iter = solve(A - lambda_guess*Id, x_iter) 可能还需要使用迭代线性求解器。

我建议将其与子空间迭代方法相结合，子空间大小至少为2。这样，在第一次迭代中，您可以找到最小和第二小的特征值lambda1和lambda2。

然后，您可以尝试lambdaguess = lambda2 + epsilon，以便输出的第一个和第二个特征向量分别对应于第二个和第三个最小特征值。（如果此迭代的第一个特征值与先前迭代的lambda2的值不同，则需要使epsilon更小并重复。在实践中，您需要测试它们之间的差异是否足够小，以考虑舍入误差和迭代方法从未精确的事实）。您重复此过程，直到获得所需的特征值。这会很慢，但您每次只使用两个特征向量。

注意：我们假设所有特征值都是不同的，否则使用通常技术解决此问题将不能得到低内存解决方案。一般来说，如果一个特征值的最大重复次数为m，则需要在内存中保存m个向量才能使子空间迭代收敛。

- Juan Carlos Ramirez