# 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). – amoeba Nov 2 '18 at 13:49

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 ...". – GeoMatt22 Sep 19 '16 at 18:39
• Yeah makes sense. Was a bit stream of consciousness :) – ilanman Sep 19 '16 at 18:45
• Better than my first thought for an answer (given the OP's definition of favorable): "Never." – GeoMatt22 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. – amoeba Nov 2 '18 at 17:15