Learn AI Create the Future — with Pranay
Main site

Dimensionality Reduction

Random projections

Squashing high-dimensional data through a completely random matrix preserves the distances between points almost perfectly — a mathematical free lunch with a proof attached.

Read these first

On this page 5
  1. Why it exists
  2. How it works
  3. A real example you have seen
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

A random projection compresses your columns using pure randomness — no learning at all — and the distances between your data points barely change.

Take a complicated wire sculpture and shine a torch on it from a completely arbitrary angle. Common sense says a careless angle should mangle the sculpture's proportions. The surprise: if what you care about is the distances between the sculpture's corner points, almost every angle preserves them roughly right. Bad angles exist, but they are astonishingly rare.

That is the entire method. Build a random recipe for blending your columns, apply it, done. No fitting, no analysis of the data, no cleverness — and a mathematical guarantee that distances survive.

Why it exists

PCA studies your data before compressing it, which costs time and memory on huge matrices. Sometimes you cannot afford the study: the data is too wide, arriving as a stream, or spread across machines. Random projection asks nothing about the data. The recipe can be generated before the data even exists.

And there is a theorem — the Johnson-Lindenstrauss lemma — behind the audacity. It says something startling. A few thousand random dimensions are enough to keep the distances between your points roughly intact. That holds no matter how many columns you started with. A million columns or ten thousand — the target size depends only on how many points you have and how much error you accept.

How it works

10,000 columns          random blend recipes           1,000 columns
row ────────────>  new col 1 = random mix of all  ──>  row, squashed
                   new col 2 = different random mix
                   ... (1,000 such mixes) ...

distances between rows:  preserved to within a few percent

Why does randomness work? Each random blend is a noisy glimpse of the data. One glimpse is unreliable. A thousand independent noisy glimpses, averaged, pin the true distances down — the same reason a thousand coin flips reliably land near half heads.

A real example you have seen

Compare two long books by taking the same random sample of fifty page numbers from each and reading only those pages. The sample is arbitrary, yet it supports a fair comparison — and the same fifty page numbers work for any pair of books. The recipe never needed to know the books.

Remember this

  • Random projection compresses without looking at the data — nothing is learned.
  • Distances between points survive, with a proven bound on the damage.
  • The compressed size depends on how many rows you have, not how many columns.

What to learn next

  • The hashing trick — random projection's zero-memory cousin.
  • Vector databases — where distance-preserving compression powers real search.
  • t-SNE — when the goal is a picture, not preserved distances.

Developer — Code and libraries.

Setup

bash
pip install scikit-learn numpy

Outputs verified with scikit-learn 1.7.2.

10,000 columns to 1,000, distances intact

randproj.py
import numpy as np
from sklearn.random_projection import GaussianRandomProjection, johnson_lindenstrauss_min_dim
from sklearn.metrics import pairwise_distances

rng = np.random.default_rng(0)
X = rng.normal(size=(300, 10000))          # 300 points, ten thousand columns

print("dims needed for 10% distortion:",
      johnson_lindenstrauss_min_dim(n_samples=300, eps=0.10))

proj = GaussianRandomProjection(n_components=1000, random_state=0)
Z = proj.fit_transform(X)

before = pairwise_distances(X)[np.triu_indices(300, k=1)]
after = pairwise_distances(Z)[np.triu_indices(300, k=1)]
ratio = after / before
print(f"shape: {X.shape} -> {Z.shape}")
print(f"distance ratio: median {np.median(ratio):.3f}, "
      f"min {ratio.min():.3f}, max {ratio.max():.3f}")
Output
dims needed for 10% distortion: 4888
shape: (300, 10000) -> (300, 1000)
distance ratio: median 1.002, min 0.918, max 1.115

The walkthrough

Read the ratio line. After compressing 10,000 columns to 1,000 random blends, every one of the 44,850 pairwise distances sits within about 11% of its original value, and the typical one within 0.2%. Nothing about the data was used to build the projection.

The helper is deliberately pessimistic. johnson_lindenstrauss_min_dim answers from the worst-case theorem: guaranteeing 10% for any 300 points needs 4,888 dimensions. We used 1,000 and still landed within 11% — real behaviour is much kinder than the guarantee. Use the helper as an upper bound, then measure, as done here.

fit_transform fits nothing from the data. The "fit" only samples the random matrix and checks shapes. That means no leakage is possible through this step, and the same fitted object must be reused so train and test pass through the same randomness.

SparseRandomProjection replaces the Gaussian recipe with mostly-zero entries (Achlioptas' trick) — several times faster, far lighter in memory, same guarantee. Prefer it in production.

Common mistakes

Expecting meaningful directions. PCA's first component means something. A random projection's columns mean nothing individually — only the geometry of the whole cloud survives. Never interpret, plot, or rank individual projected columns.

Using it on data that is not high-dimensional. Projecting 10 columns to 5 random blends destroys plenty and saves nothing. The lemma's magic needs a big starting dimension; below a few hundred columns, use PCA.

Projecting to too few dimensions because a plot wants 2. At n_components=2 the distortion is enormous — the guarantee at 300 points would demand impossible error tolerance. Random projection is for compressing 10,000 to 1,000, not for visualising. Visualisation belongs to t-SNE and UMAP.

Regenerating the matrix per batch. Two batches projected through different random matrices land in unrelated spaces. Serialise the fitted object like any model artefact.

Try it yourself

Rerun with n_components at 100, 500, 2000, 4888, printing the min and max ratio each time. Watch distortion shrink as dimensions grow, and find the smallest size your own tolerance would accept.

What to learn next

  • The hashing trick — random projection's zero-memory cousin.
  • Vector databases — where distance-preserving compression powers real search.
  • t-SNE — when the goal is a picture, not preserved distances.

Researcher — Mathematics and papers.

The lemma

Johnson and Lindenstrauss (1984): for any 0 < eps < 1 and any n points in R^d, there exists a linear map f: R^d -> R^k with

k >= 4 ln(n) / (eps^2/2 - eps^3/3)

such that for every pair u, v: (1 - eps) ||u - v||^2 <= ||f(u) - f(v)||^2 <= (1 + eps) ||u - v||^2.

Two facts deserve emphasis. First, k is independent of d — the ambient dimension appears nowhere. Second, the modern proofs are probabilistic: a random Gaussian matrix (entries N(0, 1/k)) satisfies the property with high probability, so "there exists" becomes "sample one and it almost surely works". The proof reduces to a concentration inequality for the squared norm of a projected vector (chi-squared tails), plus a union bound over the n(n-1)/2 pairs — which is where the ln(n) comes from. The bound is essentially tight: Larsen and Nelson (2017) proved k = Omega(ln(n)/eps^2) is necessary.

Cheaper matrices

  • Achlioptas (2003): entries in {+1, 0, -1} with probabilities {1/6, 2/3, 1/6} (scaled) — database-friendly, integer arithmetic, same guarantee.
  • Very sparse RP (Li, Hastie, Church, 2006): density 1/sqrt(d), giving order sqrt(d)-fold speedups with modest variance inflation.
  • FJLT (Ailon and Chazelle, 2009): randomised Hadamard transform then sparse projection, O(d log d) per vector — the fast path when d is huge.
  • The hashing trick is the implicit, memory-free member of this family, trading tightness for O(1) storage.

Where it earns its keep

Approximate nearest-neighbour search: LSH with random hyperplanes (Charikar, 2002) is JL machinery converted to hashing, underlying modern vector database indexes. Compressed sensing shares the concentration toolkit (restricted isometry property). In learning pipelines, RP is a preconditioner: project 10^6 -dimensional features to 10^3, then run anything downstream; Bingham and Mannila (2001) documented the empirical harmlessness on image and text data. Randomized SVD (Halko et al., 2011) uses RP as its first stage — project, then look — which is why sketch-then-solve is the standard pattern in large-scale numerical linear algebra.

Contrast with PCA

PCA minimises reconstruction error for this dataset; RP guarantees distance preservation for any dataset. PCA can beat RP dramatically when variance concentrates in few directions; RP cannot be beaten by an adversary choosing the data after the projection, needs no pass over the data, and parallelises with no coordination at all. When both are affordable, PCA at equal k typically preserves more useful structure — RP's edge is cost, streaming, and worst-case safety, not fidelity.

What to learn next

  • The hashing trick — random projection's zero-memory cousin.
  • Vector databases — where distance-preserving compression powers real search.
  • t-SNE — when the goal is a picture, not preserved distances.