Random Projection
Random Projection (Johnson-Lindenstrauss Dimensionality Reduction) · Also known as: random projections, Johnson-Lindenstrauss projection, sparse random projection, rastgele izdüşüm
Random projection reduces dimensionality by multiplying the data by a random matrix, relying on the Johnson-Lindenstrauss lemma (1984), which guarantees that projecting onto enough random directions approximately preserves all pairwise distances. Unlike PCA it does not analyze the data at all — the projection is random and data-oblivious — making it extremely cheap and well suited to very high-dimensional data and streaming or privacy-sensitive settings.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use random projection when dimensionality is so high that data-dependent methods like PCA are too slow or memory-heavy, when data arrive in a stream (the random matrix is fixed in advance), or when a data-oblivious, privacy-friendly reduction is desirable — text/bag-of-words, image features, genomics, and as a fast preprocessing step before clustering, nearest-neighbour search, or learning. It is extremely cheap and comes with a distance-preservation guarantee. Its trade-offs: it preserves distances only approximately (tolerance ε), it does not find or rank meaningful directions the way PCA does (so it is less interpretable and may need more target dimensions for the same fidelity), and results vary slightly with the random seed. When you need the most informative axes or maximal compression for a given fidelity, PCA is preferable; random projection wins on speed and scale.
Strengths & limitations
- Extremely fast and memory-light — a single random matrix multiply, no training.
- Theoretically grounded: the JL lemma guarantees approximate distance preservation.
- Data-oblivious, so it works for streaming and privacy-sensitive settings.
- Target dimension scales with the number of points, not the original dimension.
- Preserves distances only approximately (within tolerance ε).
- Does not identify meaningful/important directions like PCA — less interpretable.
- May need more target dimensions than PCA for the same fidelity.
- Result depends on the random seed (mildly non-deterministic).
Frequently asked
How is random projection different from PCA?
PCA finds the data-dependent directions of maximum variance via eigen-decomposition; random projection uses random, data-oblivious directions and a distance-preservation guarantee. PCA is more informative and compact per dimension but slower and memory-heavy; random projection is far cheaper and scales better, at the cost of interpretability and exactness.
How many dimensions do I need?
By the JL lemma, roughly O(ln n / ε²), where n is the number of points and ε the allowed distortion. Notably it depends on the number of points and the tolerance, not the original dimension — so very high-dimensional data still compress to a few hundred dimensions for modest ε.
Why use sparse random matrices?
Achlioptas showed that simple sparse ±1 (or mostly-zero) matrices still satisfy the JL guarantee while being much cheaper to store and multiply. This 'database-friendly' construction makes random projection fast and practical on large, high-dimensional datasets.
Sources
- Johnson, W. B., & Lindenstrauss, J. (1984). Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26, 189–206. DOI: 10.1090/conm/026/737400 ↗
- Achlioptas, D. (2003). Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4), 671–687. DOI: 10.1016/S0022-0000(03)00025-4 ↗
How to cite this page
ScholarGate. (2026, June 2). Random Projection (Johnson-Lindenstrauss Dimensionality Reduction). ScholarGate. https://scholargate.app/en/machine-learning/random-projection
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Locally Linear EmbeddingMachine learning↔ compare
- Matrix CompletionMachine learning↔ compare