python - 逼近大型对称矩阵的最高 3 个特征值和特征向量的快速方法

Question

我正在编写代码来计算 Classical Multidimensional Scaling (缩写为 MDS)一个非常大的 n by n 矩阵，在我的例子中 n = 500,000。

在 MDS 的一步中，我需要计算最高的三个 eigenvalues and their corresponding eigenvectors n 乘 n 矩阵。该矩阵称为 B 矩阵。我只需要这三个特征向量和特征值。计算大矩阵的特征向量和特征值的常用方法需要很长时间，而且我不需要很准确的答案，所以我正在寻求特征向量和特征值的估计。

一些参数:

1. B 矩阵是 symmetric , real ，相当dense
2. B 的特征值分解在理论上应该总是产生实数。
3. 我不需要完全精确的估计，只需要一个快速的估计。我需要它在几个小时内完成。
4. 我用 python 和 C++ 编写

我的问题:是否有快速估计如此大的 B 矩阵的三个最高特征向量和特征值的方法？

我的进步:我找到了一个 method of approximating the highest eigenvalue of a matrix ，但我不知道我是否可以将其概括为最高的三个。我还找到了this paper written in 1996 ，但它非常技术性，我很难阅读。

Answer 1

G. Golub 和 C.F Van Loan Matrix Computations 2nd 在第 9 章中指出 Lanczos 算法是一种选择(除了理想情况下矩阵应该是稀疏的 - 它显然也适用于非稀疏矩阵)

https://en.wikipedia.org/wiki/Lanczos_algorithm