Random Projection (JL)

Imagine you have a thousand points floating in a million-dimensional space — genome expression vectors, word embeddings, image features. Computing distances between all pairs is costly, and storing the data is painful. Is there a way to squeeze the dimensions without destroying the geometric structure that matters?

In 1984, William B. Johnson and Joram Lindenstrauss proved a striking fact: for any set of $n$ points in a high-dimensional space, a random linear projection into a space of only $k = O\!\left(\frac{\log n}{\varepsilon^2}\right)$ dimensions will preserve every pairwise distance to within a factor of $1 \pm \varepsilon$, with high probability. The target dimension depends only on how many points you have and how much distortion you can tolerate — not on the original dimension at all.

The key idea is deceptively simple: project the points onto a random subspace by multiplying by a matrix whose entries are independent Gaussian (or ±1) random variables, then rescale. Randomness, it turns out, is all the structure you need.

Below, five points live in 2D. A random unit vector (the green arrow) defines the projection direction — points are mapped to their coordinate along that axis. The table shows the original distance and projected distance for every pair, together with the distortion ratio.

<!-- {{c_demo_title}} -->
<p class="hint">{{hint_para}}</p>
<div class="canvas-wrap">
  <canvas id="cvs" width="300" height="300" title="{{canvas_title}}"></canvas>
</div>
<div class="proj-bar-wrap">
  <div class="proj-label">{{proj_label}}</div>
  <canvas id="proj" width="300" height="40" title="{{proj_bar_title}}"></canvas>
</div>
<div class="table-wrap">
  <table id="dist-table">
    <thead>
      <tr>
        <th>{{th_pair}}</th>
        <th>{{th_orig}}</th>
        <th>{{th_proj}}</th>
        <th>{{th_ratio}}</th>
      </tr>
    </thead>
    <tbody id="dist-body"></tbody>
  </table>
</div>
<div class="btns">
  <button id="btn-new" type="button">{{btn_new}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status"></div>

/* {{c_base_styles}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.5; }
.canvas-wrap { display: inline-block; border: 1px solid #cdd9e3; border-radius: 8px; overflow: hidden; }
canvas { display: block; background: #f4f7fa; cursor: crosshair; }
/* {{c_proj_styles}} */
.proj-bar-wrap { margin: .5rem 0 .3rem; }
.proj-label { font-size: .8rem; color: #555; margin-bottom: .2rem; }
#proj { border: 1px solid #cdd9e3; border-radius: 6px; background: #eef1f5; display: block; }
/* {{c_table_styles}} */
.table-wrap { overflow-x: auto; margin: .4rem 0; }
table { border-collapse: collapse; font-size: .83rem; width: 100%; min-width: 260px; }
th { background: #e8eef3; color: #1d3557; padding: .3rem .5rem; text-align: left; font-weight: 600; }
td { padding: .25rem .5rem; border-bottom: 1px solid #e4e8ed; }
tr.highlight td { background: #fff8e1; }
.ratio-ok { color: #0a7d33; }
.ratio-warn { color: #c92f3c; }
/* {{c_button_styles}} */
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin-top: .2rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Click New random direction to sample a fresh projection. Notice that most ratios stay close to 1 — rarely does a single projection crush two nearby points together or pull two far ones apart. The JL guarantee says: if you average over many random directions (or use a $k$-dimensional random subspace instead of a single axis), the worst-case distortion across all pairs shrinks rapidly as $k$ grows.

The Johnson–Lindenstrauss lemma is not just a curiosity — its bounds are essentially tight.

• Upper bound: a $k \times d$ matrix $R$ with i.i.d. $\mathcal{N}(0,1)$ entries, scaled by $1/\sqrt{k}$, maps any fixed pair of points $u, v$ so that

  $$\Pr\!\left[\,\left|\,\|Ru - Rv\|^2 - \|u - v\|^2\,\right| > \varepsilon\,\|u - v\|^2\right] \le 2e^{-(\varepsilon^2 - \varepsilon^3)k/4}.$$

  A union bound over all $\binom{n}{2}$ pairs then shows $k = O(\log n / \varepsilon^2)$ suffices to preserve every distance simultaneously.

• Lower bound: Alon (2003) showed that for $n$ points in general position, any embedding into $k$ dimensions with distortion at most $1 + \varepsilon$ requires $k = \Omega(\log n / \varepsilon^2)$. The $\log n$ factor is necessary, not an artifact of the proof.

• Faster projections: the dense Gaussian matrix costs $O(dk)$ per point. The Fast JL Transform (Ailon & Chazelle, 2006) achieves the same guarantee in $O(d \log d)$ time using a structured random matrix — a Hadamard transform followed by a sparse random sign-flipping.

• No free lunch: distance preservation is powerful but not free. The dimensionality reduction literature shows that for worst-case metrics (not Euclidean), the distortion bounds are much weaker, and exact representation can require linear dimension.

So the JL lemma gives an optimal, efficiently constructible dimension: $O(\log n / \varepsilon^2)$, achievable by pure randomness.

The JL lemma is one of the most used tools in modern data-intensive computing:

• Approximate nearest-neighbor search: project a million high-dimensional vectors into $O(\log n)$ dimensions, build a $k$-d tree or hashing structure there, and answer distance queries orders of magnitude faster — with only an $\varepsilon$ error on reported distances.
• Streaming and sketching: algorithms that see data once and must answer queries on a tight memory budget routinely use random projections. The Johnson–Lindenstrauss sketch stores $O(\log n / \varepsilon^2)$ numbers per vector instead of the full $d$-dimensional one.
• Compressed sensing: if a signal is sparse in some basis, $O(k \log(d/k))$ random measurements suffice to recover it exactly (Candès, Romberg & Tao, 2006). This is a cousin of the JL lemma applied to sparse vectors.
• Neural network training: the first layer of a random-weights network is a JL-style projection. Several theoretical results explain why random features work as initializers for neural network training.
• Graph sparsification and spectral methods: random projections compress the Laplacian of a graph while preserving spectral properties.

Wherever a high-dimensional dot product or distance appears and you need speed, the JL lemma is usually the right hammer.

The Johnson–Lindenstrauss lemma delivers a remarkable promise: take any set of $n$ points in arbitrarily high dimensions, multiply by a matrix of coin flips, and every pairwise distance survives intact — up to a factor of $1 \pm \varepsilon$ — in a space of just $O(\log n / \varepsilon^2)$ dimensions. No knowledge of the data, no careful tuning, just randomness.

This is a rare case in algorithm design where the analysis says "random is optimal." The dimension bound is tight, the construction is trivially parallelizable, and the distortion guarantee is exponentially sharp. Wherever you face a high-dimensional geometry problem, a random projection is almost always the first thing to try.