逼近大型对称矩阵的最高 3 个特征值和特征向量的快速方法
Fast methods for approximating the highest 3 eigenvalues and eigenvectors of a large symmetric matrix
我正在编写代码来计算非常大的 n by n 矩阵的 Classical Multidimensional Scaling（缩写为 MDS），在我的示例中为 n = 500,000。
在 MDS 的一步中，我需要通过 n 矩阵计算 n 的最高三个 eigenvalues and their corresponding eigenvectors。该矩阵称为 B 矩阵。我只需要这三个特征向量和特征值。计算大矩阵的特征向量和特征值的常用方法需要很长时间，而且我不需要很准确的答案，所以我正在寻求特征向量和特征值的估计。
一些参数：
B矩阵是symmetric, real, and quite dense- 理论上
B的特征值分解应该总是产生实数。
- 我不需要完全精确的估计，只需要一个快速的估计。我需要它在几个小时内完成。
- 我用 python 和 C++
编写
我的问题：是否有快速估计如此大的 B 矩阵的三个最高特征向量和特征值的方法？
我的进步：我找到了一个method of approximating the highest eigenvalue of a matrix, but I do not know if I can generalize it to the highest three. I have also found this paper written in 1996，但它技术性很强，我很难阅读。
G。 Golub 和 C.F Van Loan Matrix Computations 2nd 在第 9 章中指出 Lanczos 算法是对此的一种选择（除了理想情况下矩阵应该是稀疏的 - 它显然也适用于非稀疏矩阵）
您可以获得 B 的最高特征向量，然后使用该特征向量将数据转换为 B'。然后弹出 B' 的第一列并得到 B'' 这样你就可以获得 B'' 的最高特征向量：这些信息足以构成 B 的第二高特征向量。然后是第三个。
关于速度：您可以随机抽取那个庞大的数据集，使其成为只有 N 个项目的数据集。如果您只获得三个维度，我希望您也可以去掉大部分数据以获得特征向量的概览。你可以称它为：'electoral poll'。我无法帮助您测量错误率，但我会尝试多次抽样 1k 个项目，看看结果是否大致相同。
现在你可以得到几个'polls'的平均值来构建一个'prediction'。
查看此线程中的建议
Largest eigenvalues (and corresponding eigenvectors) in C++
按照那里的建议，您可以使用具有 C++ 接口的 ARPACK 包。
我正在编写代码来计算非常大的 n by n 矩阵的 Classical Multidimensional Scaling（缩写为 MDS），在我的示例中为 n = 500,000。
在 MDS 的一步中，我需要通过 n 矩阵计算 n 的最高三个 eigenvalues and their corresponding eigenvectors。该矩阵称为 B 矩阵。我只需要这三个特征向量和特征值。计算大矩阵的特征向量和特征值的常用方法需要很长时间，而且我不需要很准确的答案，所以我正在寻求特征向量和特征值的估计。
一些参数：
B矩阵是symmetric, real, and quite dense- 理论上
B的特征值分解应该总是产生实数。 - 我不需要完全精确的估计，只需要一个快速的估计。我需要它在几个小时内完成。
- 我用 python 和 C++ 编写
我的问题：是否有快速估计如此大的 B 矩阵的三个最高特征向量和特征值的方法？
我的进步：我找到了一个method of approximating the highest eigenvalue of a matrix, but I do not know if I can generalize it to the highest three. I have also found this paper written in 1996，但它技术性很强，我很难阅读。
G。 Golub 和 C.F Van Loan Matrix Computations 2nd 在第 9 章中指出 Lanczos 算法是对此的一种选择（除了理想情况下矩阵应该是稀疏的 - 它显然也适用于非稀疏矩阵）
您可以获得 B 的最高特征向量，然后使用该特征向量将数据转换为 B'。然后弹出 B' 的第一列并得到 B'' 这样你就可以获得 B'' 的最高特征向量：这些信息足以构成 B 的第二高特征向量。然后是第三个。
关于速度：您可以随机抽取那个庞大的数据集，使其成为只有 N 个项目的数据集。如果您只获得三个维度，我希望您也可以去掉大部分数据以获得特征向量的概览。你可以称它为：'electoral poll'。我无法帮助您测量错误率，但我会尝试多次抽样 1k 个项目，看看结果是否大致相同。
现在你可以得到几个'polls'的平均值来构建一个'prediction'。
查看此线程中的建议
Largest eigenvalues (and corresponding eigenvectors) in C++
按照那里的建议，您可以使用具有 C++ 接口的 ARPACK 包。