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)?
 A: 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:


*

*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 ? 

*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)$
A: 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:

*

*Cross-validation methods in principal component analysis: A comparison (Diana, Tommassi, 2002)

A: 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%.
A: I have never done this but my intuition suggests that the answer would depend to the extent to which the covariance matrix for the 500 data points is 'different' from the out-of-sample data. If the out-of-sample covariance matrix is very different then clearly the projection matrix of those points would be different than the projection matrix that emerges from the in-sample data. Thus, to the extent that the covariance matrix for the in-sample and out-of-sample data is 'similar' the results should be about the same.
The above intuition suggests that you should carefully select the 500 in-sample points so that the resulting covariance matrices are as identical as possible for the in-sample and the out-of-sample.
