5
$\begingroup$

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

$\endgroup$

4 Answers 4

3
$\begingroup$

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)$

$\endgroup$
3
  • 1
    $\begingroup$ @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. $\endgroup$
    – whuber
    Sep 21, 2010 at 14:11
  • $\begingroup$ @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 ? $\endgroup$
    – user603
    Sep 21, 2010 at 15:41
  • $\begingroup$ See here for a recently developed method for approximating the eigenvectors of a large matrices: projecteuclid.org/… $\endgroup$
    – vqv
    Dec 20, 2010 at 0:09
2
$\begingroup$

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%.

$\endgroup$
7
  • $\begingroup$ 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...) $\endgroup$ Sep 20, 2010 at 21:38
  • $\begingroup$ @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. $\endgroup$
    – ebony1
    Sep 20, 2010 at 22:15
  • $\begingroup$ @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. $\endgroup$
    – whuber
    Sep 20, 2010 at 22:18
  • 1
    $\begingroup$ @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 XX' (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. $\endgroup$
    – ebony1
    Sep 21, 2010 at 11:21
  • 4
    $\begingroup$ @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. $\endgroup$
    – whuber
    Sep 21, 2010 at 14:08
2
$\begingroup$

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:

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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