问题描述
我有一个〜3000×3000协方差矩阵,我计算特征值 - 特征向量分解(它是一个OpenCV矩阵,我使用 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 int idx = n * eigValIdx + 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个向量快的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!