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