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.

  • 2
    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 at 13:49
up vote 7 down vote accepted

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.
  • 1
    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
  • 1
    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 at 17:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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