Dimension Reduction Taxonomy - 11. Random Projection and the Johnson-Lindenstrauss Lemma

11. Random Projection and the Johnson-Lindenstrauss Lemma

Random Projection is a computationally cheap technique grounded in the Johnson-Lindenstrauss Lemma. It states that high-dimensional data can be projected into $O(\log n/{\epsilon }^2)$ dimensions while approximately preserving pairwise distances.

This figure illustrates the concept of Random Projection, one of the simplest and fastest dimensionality reduction techniques. On the left, we have high-dimensional data points (blue circles) in a space of dimension p. The arrow represents the application of a random matrix R of size k × p, where k is the target lower dimension. The matrix R can be Gaussian (entries from N(0,1)) or sparse (entries from {-1, 0, 1} with controlled sparsity). The result on the right is the data mapped to k dimensions (green circles). The Johnson-Lindenstrauss lemma guarantees that with high probability, the pairwise distances between points are preserved within a factor of (1 ± ε), as long as k is at least $O(\log n/{\epsilon }^2)$. This is a powerful result because k is independent of the original dimension p. Random projection is extremely fast because it only involves matrix multiplication, and for sparse matrices, this can be even faster. It is used extensively in streaming data, approximate nearest neighbor search, and as a preprocessing step for more expensive methods like PCA.

11.1 The Johnson-Lindenstrauss Lemma

The JL lemma states that for any set of n points, there exists a map to $k=O(\log n/{\epsilon }^2)$ dimensions such that:

The target dimension is independent of the original dimension.

The lemma's proof uses the fact that random projections are almost isometries. The constant factor in the O(log n) term is small, typically around 4. For example, to preserve distances within 10% (ε=0.1) for n=10,000 points, k≈4600, which is far smaller than the original dimension if p is large. This makes random projection a practical tool for dimensionality reduction. The lemma is also the theoretical basis for compressive sensing, where signals are recovered from fewer measurements. In practice, random projection is often used with the Gaussian or Achlioptas sparse matrix, and the results are surprisingly good for many applications.

11.2 Practical Implementation

Generate a random matrix R (size p × k) with Gaussian or sparse entries, and compute:

This is extremely fast and memory-efficient.

In practice, the random matrix can be generated on the fly or stored once. For sparse matrices, the multiplication can be done in O(n * p * s) where s is the sparsity (e.g., s=3 for the Achlioptas matrix). This makes random projection scalable to datasets with millions of features. Libraries like scikit-learn provide efficient implementations. Random projection is often used as a preprocessing step for k-means clustering or nearest neighbor search, where the reduced dimension significantly speeds up computation with minimal loss in accuracy. It is also a key component in the "randomized SVD" algorithm, which approximates the SVD of large matrices.

Applications

• Accelerating distance-based algorithms (K-means, KNN).
• Fast Fourier transform and signal processing.
• Compressive sensing.
• Preprocessing for extremely high-dimensional datasets.

Strengths and limitations