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.
 A: 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.
A: 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.
A: 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.

