3
$\begingroup$

For computational efficiency in PCA, evaluation of covariance matrix is done as $C = AA^T$ instead of original $C=A^TA$. How can that be justified? What steps are needed then to recover the original information? Although I can find the beauty and idea of PCA algorithm, still having hard time understanding some concepts.

Note: Here $C$ is the covariance matrix and $A$ is the set of data vectors represented in a matrix.

$\endgroup$
3
$\begingroup$

Why use these matrix product at all?

Just compute the SVD, using Golub-Kahan or better,

$$A=USV^T,$$

$S$ diagonal, with non-negative diagonal, $U,V$ orthogonal, then you automatically also know the eigenvector decompositions

$$AA^T=U(SS^T)U^T\text{ and }A^TA=V(S^TS)V^T.$$


Representing the matrix as $A=\sum_{k=1}^r σ_k u_kv_k^T$ also allows you to see how the conversion that you asked about works. If $AA^T$ is diagonalized, the result can be written as $AA^T=\sum_{k=1}^r σ_k^2 u_ku_k^T$, the pairs $(λ_k=σ_k^2, u_k)$ are the result of the diagonalization. Since the vectors $u_k$ are orthonormal, one gets $A^Tu_k=σ_k v_k$, so that in turn $v_k=\frac1{\sqrt{λ_k}}A^Tu_k$, where the $v_k$ are the orthonormal eigenvectors of $A^TA$.

$\endgroup$
  • $\begingroup$ OK good to know that. This is just another computationally better method, right? $\endgroup$ – dexterdev May 9 '14 at 14:33
  • 1
    $\begingroup$ Yes. Since the matrix product also squares the condition number, processing the unsquared matrix is numerically more stable. $\endgroup$ – LutzL May 9 '14 at 15:04
  • $\begingroup$ But I am a beginner looking at the original algorithm and my doubt persists. $\endgroup$ – dexterdev May 9 '14 at 15:12
  • $\begingroup$ @LutzL I think one reason why SVD is sometimes avoided in practice is that if the dimensionality of the data is very high (e.g. let's say you have 1'000 data samples, each with 90'000 dimensions). In this case SVD would probably be very slow, while computing AA^t is more feasible (which ends up a 1000x1000 matrix) and then an eigendecomposition on this 1000x1000 matrix is also fast again. $\endgroup$ – Ela782 Aug 19 '17 at 20:09

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.