2
$\begingroup$

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

  1. Calculate data vectors' covariance matrix C.
  2. Solve det(C - e*I) = 0, to find matrix C's eigenvalues e.
  3. Calculate matrix C's eigenfunctions (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++?

$\endgroup$
6
$\begingroup$

This is not done by solving the polynomial equation, but rather by iterative operations on matrices. Start by having a look on

  • the Nipals algorithm to compute only the first few PC this seems very simple and clear ;

  • the QR decomposition if you want all PC (although it has never been very clear to me that it is or should be faster).

Of course there are plenty of codes for this, QR decomposition is in LAPACK, and with LAPACK you won’t have much problems to implement Nipals if you can’t google anything satisfying.

$\endgroup$
5
  • $\begingroup$ Thanks.Is it possible that different decomposition methods give different sets of eigenvectors for the same matrix? Secondly, regarding QR decomposition: Are the eigenvectors the columns of the matrix Q? How do I find their eigenvalues? $\endgroup$ – Bliss Jan 5 '12 at 20:47
  • $\begingroup$ No, it is not as simple, you need to iterate. Start with $X_1$ (symmetric), compute $Q_1, R_1$ such that $X_1 = Q_1 R_1$, and let $X_2 = R_1 Q_1$ ; iterate (pass from $X_n = Q_n R_n$ to $X_{n+1} = R_n Q_n$), $X_n$ will converge to a diagonal matrix with the eigenvalues on the diagonal. The eigenvectors are the columns of $\prod_i Q_i$ (you don’t store all the $Q_i$, just compute the new product each time). $\endgroup$ – Elvis Jan 5 '12 at 21:24
  • $\begingroup$ Thanks. Just to make sure I understand and make it well: I'm using the Gram-Schmidt algorithm to perform QR decomposition. I should decompose the original matrix X1 (which is a covariance matrix and hence symmetric) to Q1*R1, then calculate a matrix X2 = R1*Q1, QR-decompose X2 to Q2*R2, calculate a matrix X3 = R2*Q2 and so on... until a diagonal matrix Xn is received? Thanks again. $\endgroup$ – Bliss Jan 6 '12 at 10:26
  • $\begingroup$ @YanRaf yes! I'll add an example in the answer in a moment. $\endgroup$ – Elvis Jan 6 '12 at 12:38
  • $\begingroup$ Finally I answered to your other question... $\endgroup$ – Elvis Jan 6 '12 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.