1
$\begingroup$

I am wondering if there exists an efficient method to compute PCA. I am drafting the question into a presudo code:

matrix = []
pca = [] * 9999999
for i in range (0, 9999999):
    matrix = add_one_new_row(matrix)
    pca[i].append(do_pca(matrix))

I will need to calculate PCA each time for an incrementally growing matrix. While the above method would give me the PCA each time, I am just wondering if there exists a more efficient algorithm on this, since when calculating PCA for nth time, I have all the previously calculated PCA already.

$\endgroup$
2
$\begingroup$

The PCA components are eigenvectors of $X^TX$. Adding a row to $X$ corresponds to a rank 1 update of $X^TX$: $$\begin{pmatrix}X \\ v^T\end{pmatrix}^T \begin{pmatrix}X \\ v^T\end{pmatrix} = X^TX + vv^T.$$ You can use the Bunch–Nielsen–Sorensen formula to get the eigenvalues of $X^TX + vv^T$ based on the eigenvalues of $X^TX$. To apply the formula, you first have to perform a linear transformation to $X^TX$ to make it diagonal (full details in this publication), which may null the speed gains. An alternative formula is presented in this paper.

$\endgroup$
  • $\begingroup$ Aren't the all the PCA components eigenvectors of $X^TX$? Thus, PCA analysis has already effectively diagonlized $X^TX$. $\endgroup$ – Acccumulation Sep 12 '18 at 15:10
  • $\begingroup$ @Acccumulation if he is interested in all components, you are right $\endgroup$ – LinAlg Sep 12 '18 at 15:18

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.