PCA: Find covariance matrix’s eigenvalues: solving a polynomial of degree N

algorithmmathmatrixpca

If I understand correctly, PCA's principle is very simple:

Calculate data vectors' covariance matrix C.
Solve det(C – e***I) = 0, to find matrix **C's eigenvalues e.
Calculate matrix C's eigenvectors (from those eigenvalues).

FIRST: Is this description correct?

SECOND: Any algorithm for machine-solving of the polynomial equation det(C – e***I) = 0 ?
I understand that this is a general math question (finding roots of a polynomial of degree **n).

THIRD: Are there any simple implementations of PCA in C/C++

Thanks much.

Best Answer

First of all, in order to find eigenvalues there is not need to solve equation you just mentioned. There is such thing as eigendecomposition of a matrix
Second, the covariance matrix is symmetric and positive semi-definite, so eigendecomposition for this matrix is equal to singular value decomposition.
For both mentioned decompositions there is a lot of free and proprietary implementations (the state of the art implemenation is LAPACK).
There is a lot of libraries that contains PCA. If commercial implementations are suitable you can try FinMath from RTMath or NMath from CenterSpace (both for .NET). Otherwise you can try GSL or some other library (there are several questions on StackOverflow that contains more complete list of numerical libraries).

Related Solutions

C++ find eigenvalues and eigenvectors of matrix

If someone needs this, here how I did it

    Eigen::EigenSolver<Eigen::MatrixXf> eigensolver;
    eigensolver.compute(covmat);
    Eigen::VectorXf eigen_values = eigensolver.eigenvalues().real();
    Eigen::MatrixXf eigen_vectors = eigensolver.eigenvectors().real();
    std::vector<std::tuple<float, Eigen::VectorXf>> eigen_vectors_and_values; 

    for(int i=0; i<eigen_values.size(); i++){
        std::tuple<float, Eigen::VectorXf> vec_and_val(eigen_values[i], eigen_vectors.row(i));
        eigen_vectors_and_values.push_back(vec_and_val);
    }
    std::sort(eigen_vectors_and_values.begin(), eigen_vectors_and_values.end(), 
        [&](const std::tuple<float, Eigen::VectorXf>& a, const std::tuple<float, Eigen::VectorXf>& b) -> bool{ 
            return std::get<0>(a) <= std::get<0>(b); 
    });
    int index = 0;
    for(auto const vect : eigen_vectors_and_values){
        eigen_values(index) = std::get<0>(vect);
        eigen_vectors.row(index) = std::get<1>(vect);
        index++;
    }

Here covmat in which eigenvectors and eigenvalues to be found out. Also, I sort them according to descending order which we do the most of the times. One important thing is that when you selecting which eigendecomposition technique is to be used to be careful because those are not doing the same way. You may find out more information here [https://eigen.tuxfamily.org/dox/group__Eigenvalues__Module.html ]

Best Answer

Related Solutions

C++ find eigenvalues and eigenvectors of matrix

Related Topic