c++ - una - valores propios y vectores

C++ eigenvalue/vector descomposición, solo necesita primero n vectores rápidamente

Question

Tengo una matriz similar a la covarianza de ~ 3000x3000 en la que computo la descomposición eigenvalue-eigenvector (es una matriz OpenCV, y uso cv::eigen() para hacer el trabajo).

Sin embargo, en realidad solo necesito, por ejemplo, los primeros 30 valores / vectores propios, no me importa el resto. Teóricamente, esto debería permitir acelerar el cálculo de manera significativa, ¿verdad? Quiero decir, eso significa que tiene 2970 vectores propios menos que necesitan ser computados.

¿Qué biblioteca de C ++ me permitirá hacer eso? Tenga en cuenta que el método eigen() OpenCV tiene los parámetros para eso, pero la documentación dice que se ignoraron, y yo mismo lo probé, de hecho se ignoran: D

ACTUALIZACIÓN: Me las arreglé para hacerlo con ARPACK. Me las arreglé para compilarlo para windows, e incluso para usarlo. Los resultados parecen prometedores, se puede ver una ilustración en este ejemplo de juguete:

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

Los resultados son:

9.4298, 24.24059

para los valores propios, y

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

para los 2 eigenvectores respectivamente (un eigenvector por fila) El código no encuentra 3 eigenvectores (solo puede encontrar 1-2 en este caso, un assert () se asegura de eso, pero bueno, eso no es un problema).

Answer 1

En this artículo, Simon Funk muestra una manera simple y efectiva de estimar una descomposición de valor singular (SVD) de una matriz muy grande. En su caso, la matriz es escasa, con dimensiones: 17,000 x 500,000.

Ahora, mirando here , describe cómo la descomposición del valor propio se relaciona estrechamente con la SVD. Por lo tanto, podría beneficiarse de considerar una versión modificada del enfoque de Simon Funk, especialmente si su matriz es escasa. Además, su matriz no solo es cuadrada sino también simétrica (si eso es lo que quiere decir con covarianza), lo que probablemente conduce a una simplificación adicional.

... Solo una idea :)