C++ Eigenwert/Vektorzerlegung, brauche nur zuerst n Vektoren schnell

Question

Ich habe eine ~ 3000x3000 Kovarianz-ähnliche Matrix, auf der ich die Eigenwert-Eigenvektor-Zerlegung berechnen (es ist eine OpenCV-Matrix, und ich verwende cv::eigen(), um die Arbeit zu erledigen).

Allerdings brauche ich eigentlich nur die ersten 30 Eigenwerte/Vektoren, mir ist der Rest egal. Theoretisch sollte dies erlauben, die Berechnung signifikant zu beschleunigen, oder? Ich meine, das heißt, es hat 2970 Eigenvektoren weniger, die berechnet werden müssen.

Welche C++ Bibliothek erlaubt mir das zu tun? Bitte beachten Sie, dass die OpenCV eigen() Methode die Parameter für das macht, aber die Dokumentation sagt sie ignoriert werden, und ich getestet es selbst, werden sie in der Tat ignoriert: D

UPDATE: ich es geschafft mit ARPACK. Ich habe es geschafft, es für Windows zu kompilieren und sogar zu benutzen. Die Ergebnisse sind vielversprechend, eine Darstellung kann in diesem Spielzeug Beispiel zu sehen:

#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; 
    } 

Die Ergebnisse sind:

9.4298, 24.24059 

für die Eigenwerte und

-0.523207, -0.83446237, -0.17299346 
0.273269, -0.356554, 0.893416 

für die 2 Eigenvektoren bzw. (ein Eigenvektor pro Zeile) Der Code kann 3 Eigenvektoren nicht finden (in diesem Fall kann er nur 1-2 finden, eine assert() stellt das sicher, aber das ist kein Problem).

Answer 1

Im Artikel this Artikel zeigt Simon Funk eine einfache, effektive Möglichkeit, eine Singular Value Decomposition (SVD) einer sehr großen Matrix zu schätzen. In seinem Fall ist die Matrix spärlich, mit den Dimensionen: 17.000 x 500.000.

Nun, suchen here, beschreibt, wie Eigenwertzerlegung eng mit SVD verwandt ist. Daher können Sie davon profitieren, eine modifizierte Version von Simon Funks Ansatz in Betracht zu ziehen, besonders wenn Ihre Matrix spärlich ist. Außerdem ist Ihre Matrix nicht nur quadratisch, sondern auch symmetrisch (wenn Sie das mit Kovarianz-ähnlich meinen), was wahrscheinlich zu einer zusätzlichen Vereinfachung führt.

... Nur eine Idee :)