# PCA on out-of-sample data

We know that the projection matrix learned by PCA can be applied to out-of-sample data points to get their low-dimensional embedding. However, how reliable are these embeddings expected to be, as compared to the embedding obtained from PCA with these out-of-sample points combined with the original data?

Consider this hypothetical pseudo out-of-sample setting: Let's say I have 1000 data points and I want to do PCA on them. Can I instead do PCA on maybe just 500 of them (in order to have some computational savings) and then use the learned projection matrix to get the embedding of the rest of the points as well (by treating them as out-of-sample data)?

-

Following the comments exchange with Ebony (see Whuber's answer). I gather that in Ebony's application, $p$ is much larger than $n$ which is itself very large. In this case the complexity of computing the eigen decomposition is in the order of $O(n^3)$. Two solutions spring to mind:

1. partial decomposition: assuming $p$ is very large, it could be the case that the full eigen-decomposition is not needed. If only the $k$ largest eigen values (and corresponding vectors) are needed, presumably they could be obtained with complexity near $O(nk^2)$. Would such an algorithm be a solution to your problem ?

2. Full decomposition: in this case it may be better to draw $J$ random sub-samples of your observations of size $n_0$ suitably smaller than $n$ and compute $J$ pca decompositions. That would in turn give you $J$ values of each eigen values/vector which could be used to establish the sampling distribution of there population values (and there means would be a good estimator of the population eigen values/vectors). Given the $n^3$ complexity, this could be made to be much faster (by appropriately choosing $n_0$). A second benefit is that this procedure can be run in parallele across $m$ cores/computers yielding an overall complexity of $O(jm^{-1}n_0^3)$

-
@2 is clever. It might even be better to draw correlated random subsamples: e.g., randomly partition the data into $k$ parts of approximately $n/k$ values each and run $k$ PCAs for a computational cost of only $1 / k^2$ of a full PCA. –  whuber Sep 21 '10 at 14:11
@Whuber:> thanks. However i have two questions: a) PCA on the full dataset is not the same as the mean of PCA on the parts (do you know of a way to recover the 'total-sample' pca from the 'partial-sample' ones?). b) wouldn't we (under your proposal) lose the interpretation of the 'partial-sample' PCA in terms of sampling variation ? In other words, do the distribution of the 'partial-sample' pca constructed from correlated sample have a statistical interpretation ? –  user603 Sep 21 '10 at 15:41
See here for a recently developed method for approximating the eigenvectors of a large matrices: projecteuclid.org/… –  vqv Dec 20 '10 at 0:09

This isn't unlike a model selection problem where the goal is to arrive at something close to the "true dimensionality" of the data. You could try a cross validation approach, say 5-fold CV with your 500 data points. This will give you a reasonable metric of generalization error for out-of-sample data. The following paper has a nice survey and review of related methods:

-

What computational savings? The PCA computation is based on the covariance (or correlation) matrix, whose size depends on the number of variables, not the number of data points. The calculation of a covariance matrix is fast. Even if you were doing PCA repeatedly (as part of a simulation, for instance), reducing from 1000 data points to 500 wouldn't even reduce the time by 50%.

-
i.e. the data matrix is m-by-n, where m is (usually) greater than n. Forming the covariance matrix from that will always give you an n-by-n matrix no matter how you increase or decrease m. (That's part of why using the normal equations for least-squares seduces a lot of people...) –  Ｊ. Ｍ. Sep 20 '10 at 21:38
@whuber: Well, computing the sample covariance matrix does depend on the number of data points as well and this computation costs something like O(N*P^2) for N data points having P features each. Besides, many of the fast iterative algorithms for PCA (e.g., the Expectation Maximization algorithm for PCA) have a time complexity dependent on N. It can really make a difference if N is large. So one can't say in general that the computational complexity will not at all depend on the number of data points. –  ebony1 Sep 20 '10 at 22:15
@ebony1: But O(N*P^2) is O(N), which is exactly what I was saying. If your N really is around 1000, you can't improve computational performance (which is already going to be fast unless P is huge) by more than a factor of 2. In most cases that's hardly worth sweating over and in this case, for reasons ably pointed out in your problem statement, it seems like subsampling may not be a good idea. –  whuber Sep 20 '10 at 22:18
@kwak: Okay, consider this -- if P >> N, then it's suggested that you do PCA using the eigen-decomposition of X'*X (which is NxN) rather of the covariance matrix X*X' (which is PxP). In this setting, the computational complexity is going to be O(N^3). If N is reasonably large (even though smaller than P) I don't think you can ignore the cubic complexity. –  ebony1 Sep 21 '10 at 11:21
@ebony1: It is true that the situation changes when P >> N. That's an interesting refinement of your original problem, because in effect any model is going to be a gross overfitting: more explanatory variables than data. That does not augur well for the prospects of obtaining stable results via subsampling. At a minimum, it points to the importance of retaining as much data as possible. –  whuber Sep 21 '10 at 14:08