C ++特征值/向量分解，只需要前n个向量快 [英] C++ eigenvalue/vector decomposition, only need first n vectors fast
问题描述
cv :: eigen（） 然而，我实际上只需要前30个特征值/向量，我不在乎其余的。理论上，这应该允许显着加快计算，对吧？我的意思是，这意味着它有2970个特征向量少需要计算。
哪个C ++库将允许我这样做？请注意OpenCV的 eigen（）方法有参数，但文档说他们被忽略，我自己测试，他们确实被忽略：D
UPDATE：
我设法使用ARPACK。我设法为Windows编译，甚至使用它。结果看起来很有前景，在这个玩具示例中可以看到一个例子：
#includeardsmat.h
#includeardssym.h
int n = 3; //问题的维度。
double * EigVal = NULL; // Eigenvalues。
double * EigVec = NULL; //按顺序存储特征向量。
int lowerHalfElementCount =（n * n + n）/ 2;
//整个矩阵：
/ *
2 3 8
3 9 -7
8 -7 19
* /
double * lower = new double [lowerHalfElementCount]; //下半部分矩阵
//用COLUMN major填充（即一行接一行，总是从对角元素开始）
lower [0] = 2; lower [1] = 3; lower [2] = 8; lower [3] = 9; lower [4] = -7; lower [5] = 19;
// params：dimensions（即width / height），数组的下半部分或上半部分（顺序，行主要），'L'或'U'代表上或下
ARdsSymMatrix< double> ; mat（n，lower，'L'）;
//定义特征值问题。
int noOfEigVecValues = 2;
// int maxIterations = 50000000;
// ARluSymStdEig< double> dprob（noOfEigVecValues，mat，LM，0，0.5，maxIterations）;
ARluSymStdEig< double> dprob（noOfEigVecValues，mat）;
//查找特征值和特征向量。
int converged = dprob.EigenValVectors（EigVec，EigVal）;
for（int eigValIdx = 0; eigValIdx< noOfEigVecValues; eigValIdx ++）{
std :: cout< 特征值：< EigVal [eigValIdx] \\\
Eigenvector：;
for（int i = 0; i
std :: cout<< EigVec [idx] ;
}
std :: cout<< std :: endl;
}
结果是：
对于特征值，
9.4298，24.24059
/ p>
-0.523207，-0.83446237，-0.17299346
0.273269，-0.356554，0.893416
代码找不到3个特征向量在这种情况下，assert（）确保这一点，但是，这不是问题）。
解决方案 href =http://sifter.org/~simon/journal/20061211.html =nofollow>这篇文章，Simon Funk展示了一种简单有效的方法来估计奇异值分解（SVD）的一个非常大的矩阵。在他的情况下，矩阵是稀疏的，尺寸：17,000×500,000。
现在，查看这里 ，描述了如何特征值分解与SVD密切相关。因此，你可能会从考虑一个修改版本的Simon Funk的方法，特别是如果你的矩阵是稀疏的。此外，你的矩阵不仅是正方形，而且是对称的（如果这是你的意思是协方差），这可能导致额外的简化。
...一个想法：）
I have a ~3000x3000 covariance-alike matrix on which I compute the eigenvalue-eigenvector decomposition (it's a OpenCV matrix, and I use cv::eigen() to get the job done).
However, I actually only need the, say, first 30 eigenvalues/vectors, I don't care about the rest. Theoretically, this should allow to speed up the computation significantly, right? I mean, that means it has 2970 eigenvectors less that need to be computed.
Which C++ library will allow me to do that? Please note that OpenCV's eigen() method does have the parameters for that, but the documentation says they are ignored, and I tested it myself, they are indeed ignored :D
UPDATE:
I managed to do it with ARPACK. I managed to compile it for windows, and even to use it. The results look promising, an illustration can be seen in this toy example:
#include "ardsmat.h"
#include "ardssym.h"
int n = 3; // Dimension of the problem.
double* EigVal = NULL; // Eigenvalues.
double* EigVec = NULL; // Eigenvectors stored sequentially.
int lowerHalfElementCount = (n*n+n) / 2;
//whole matrix:
/*
2 3 8
3 9 -7
8 -7 19
*/
double* lower = new double[lowerHalfElementCount]; //lower half of the matrix
//to be filled with COLUMN major (i.e. one column after the other, always starting from the diagonal element)
lower[0] = 2; lower[1] = 3; lower[2] = 8; lower[3] = 9; lower[4] = -7; lower[5] = 19;
//params: dimensions (i.e. width/height), array with values of the lower or upper half (sequentially, row major), 'L' or 'U' for upper or lower
ARdsSymMatrix<double> mat(n, lower, 'L');
// Defining the eigenvalue problem.
int noOfEigVecValues = 2;
//int maxIterations = 50000000;
//ARluSymStdEig<double> dprob(noOfEigVecValues, mat, "LM", 0, 0.5, maxIterations);
ARluSymStdEig<double> dprob(noOfEigVecValues, mat);
// Finding eigenvalues and eigenvectors.
int converged = dprob.EigenValVectors(EigVec, EigVal);
for (int eigValIdx = 0; eigValIdx < noOfEigVecValues; eigValIdx++) {
std::cout << "Eigenvalue: " << EigVal[eigValIdx] << "\nEigenvector: ";
for (int i = 0; i < n; i++) {
int idx = n*eigValIdx+i;
std::cout << EigVec[idx] << " ";
}
std::cout << std::endl;
}
The results are:
9.4298, 24.24059
for the eigenvalues, and
-0.523207, -0.83446237, -0.17299346
0.273269, -0.356554, 0.893416
for the 2 eigenvectors respectively (one eigenvector per row)
The code fails to find 3 eigenvectors (it can only find 1-2 in this case, an assert() makes sure of that, but well, that's not a problem).
解决方案 In this article, Simon Funk shows a simple, effective way to estimate a singular value decomposition (SVD) of a very large matrix. In his case, the matrix is sparse, with dimensions: 17,000 x 500,000.
Now, looking here, describes how eigenvalue decomposition closely related to SVD. Thus, you might benefit from considering a modified version of Simon Funk's approach, especially if your matrix is sparse. Furthermore, your matrix is not only square but also symmetric (if that is what you mean by covariance-like), which likely leads to additional simplification.
... Just an idea :)
这篇关于C ++特征值/向量分解，只需要前n个向量快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
