C++ autovalore/scomposizione vettoriale, servono solo i primi n vettori veloci

Question

Ho una matrice di covarianza simile a 3000x3000 su cui calcolo la scomposizione autovalore-autovettore (è una matrice OpenCV, e io uso cv::eigen() per portare a termine il lavoro).

Tuttavia, in realtà ho solo bisogno dei, diciamo, i primi 30 autovalori/vettori, non mi interessa il resto. In teoria, questo dovrebbe consentire di velocizzare il calcolo in modo significativo, giusto? Voglio dire, significa che ha 2970 autovettori meno che devono essere calcolati.

Quale libreria C++ mi consente di farlo? Si prega di notare che il metodo di OpenCV eigen() non ha i parametri per questo, ma la documentazione dice che sono ignorati, e ho provato io stesso, essi sono infatti ignorati: D

UPDATE: sono riuscito a farlo con ARPACK. Sono riuscito a compilarlo per Windows e persino a usarlo. I risultati sembrano promettenti, un'illustrazione può essere visto in questo esempio giocattolo:

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

I risultati sono:

9.4298, 24.24059 

per gli autovalori, e

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

rispettivamente per le 2 autovettori (un autovettore per riga) Il codice non riesce a trovare 3 autovettori (può trovare solo 1-2 in questo caso, un assert() lo assicura, ma beh, non è un problema).

Answer 1

Nell'articolo this, Simon Funk mostra un modo semplice ed efficace per stimare una singola decomposizione di valore (SVD) di una matrice molto grande. Nel suo caso, la matrice è sparsa, con dimensioni: 17.000 x 500.000.

Ora, guardando here, descrive come la scomposizione dell'autovalore è strettamente correlata a SVD. Pertanto, potresti trarre vantaggio dal prendere in considerazione una versione modificata dell'approccio di Simon Funk, specialmente se la tua matrice è scarsa. Inoltre, la tua matrice non è solo quadrata ma anche simmetrica (se questo è ciò che intendi per covarianza), il che probabilmente porta a una semplificazione aggiuntiva.

... Solo un'idea :)