Random Projections
by Johnson-Lidenstrauss Lemma (see Achlioptas2003) know that
- we can always embed $N$ points into a subspace with dimensionality $\log N$
- with little distortion on pair-wise distances.
- so let’s do a very simple embedding
- pick up a random subspace $S$ and project all data on $S$
References
- Achlioptas, Dimitris. “Database-friendly random projections: Johnson-Lindenstrauss with binary coins.” 2003. [http://www.sciencedirect.com/science/article/pii/S0022000003000254]