# PCA vs. random projection

In what situations would it be more favorable to use random projection to reduce the dimensionality of a dataset as opposed to PCA? By more favorable, I mean preserve the distances between points of the dataset.

• This very impressive work culturalanalytics.org/2018/09/… uses random projection instead of PCA and gives some arguments for why they prefer it (even apart from the speed issue). Nov 2 '18 at 13:49
• It is often sensible to use more than one random projection in order to gain stability and precision from aggregation, maybe also to explore variability. There's only one set of principal components so they can't be used for that. Aug 21 '20 at 13:42

PCA maintains the best possible projection.

Some reasons you would use random projections are:

• With very high dimensions, if speed is an issue, then consider that on a matrix of size $$n \times k$$, PCA takes $$O(k^2 \times n+k^3)$$ time, whereas a random projection takes $$O(nkd)$$, where you're projecting on a subspace of size $$d$$.
• With a sparse matrix its even faster.
• The data may well be low-dimensional, but not in a linear subspace. PCA assumes this.
• Random projection are also quite fast for reducing the dimension of a mixture of Gaussians.
• If the data is very large, you don't need to hold it in memory for a random projections, whereas for PCA you do.
• In general PCA works well on relatively low dimensional data.
• This seems reasonable. Just to make it a more direct answer to the question as posed (i.e. last sentence), you might consider a slight re-org? For example, start with the first sentence of your last bullet, but then transition with something like "Some reasons you would use random projections are ...". Sep 19 '16 at 18:39
• Yeah makes sense. Was a bit stream of consciousness :) Sep 19 '16 at 18:45
• Better than my first thought for an answer (given the OP's definition of favorable): "Never." Sep 19 '16 at 18:47
• Wouldn't an answer to this question need to mention Johnson-Lindenstrauss lemma?.. Here is a friendly exposition of JL: web.ma.utexas.edu/users/rachel/madison14.pdf. Here is a similar question on CStheory.SE: cstheory.stackexchange.com/questions/21487/…. But it does not really make it clear to me. Nov 2 '18 at 17:15
• Note that PCA is only the "best possible projection" according to it's implied variance-based objective function. In fact it can be quite bad in certain situations with outliers (although random projections wouldn't normally be the first choice to repair that). Aug 21 '20 at 13:39

If one only wants to approximate pairwise Euclidean distance between points (which may be useful for downstream computation like t-SNE) but the dimensionality makes computing the pairwise Euclidean distance prohibitively expensive, the Johnson-Lindenstrauss lemma makes random projections more suitable than PCA. For $$n$$ points in $$d$$ dimensions projection to $$\frac{log(n)}{\epsilon^2}$$ preserves the Euclidean distance between points to $$1\pm \epsilon$$ with high probability. I don’t know of any similar guarantees from PCA.

I would add another reason which is valid for an online setting: PCA might give you the best projection for some initial training data but it might become arbitrarily worse as time goes by and new data arrives with an "evolved" distribution. Random projections gives you a kind of probabilistic warranty against that situation. Of course, eventually k might become too low if d is increasing over time but, anyway, in this scenario of continuously learning from large streams of data, I believe random projections are a sensible and efficient approach.