The Real Complexity of the JL Lemma

Introduction

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.

Try It

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.

<!-- Random Projection (JL Lemma) interactive demo -->
<p class="hint">Drag any colored point to move it. The green dashed line is the random projection direction. The bar below shows where each point lands on that axis. Watch the distortion ratios in the table.</p>
<div class="canvas-wrap">
  <canvas id="cvs" width="300" height="300" title="2D point canvas — drag points to reposition"></canvas>
</div>
<div class="proj-bar-wrap">
  <div class="proj-label">Projected positions (1D):</div>
  <canvas id="proj" width="300" height="40" title="1D projection bar"></canvas>
</div>
<div class="table-wrap">
  <table id="dist-table">
    <thead>
      <tr>
        <th>Pair</th>
        <th>Orig. dist.</th>
        <th>Proj. dist.</th>
        <th>Ratio</th>
      </tr>
    </thead>
    <tbody id="dist-body"></tbody>
  </table>
</div>
<div class="btns">
  <button id="btn-new" type="button">New random direction</button>
  <button id="btn-reset" type="button" class="ghost">Reset points</button>
</div>
<div class="status" id="status"></div>

/* Base layout and typography */
* { 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; }
/* Projection bar 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; }
/* Distance 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; }
/* Button and status 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Johnson–Lindenstrauss demo: 5 points in 2D, projected to 1D along a random unit vector. */
/* The ratio pd/d measures how much a single projection distorts each pairwise distance. */

const CVS = document.getElementById('cvs');
const CTX = CVS.getContext('2d');
const PROJ = document.getElementById('proj');
const PCTX = PROJ.getContext('2d');
const W = CVS.width, H = CVS.height;

/* Five labeled points in normalized [0,1]^2 coordinates */
const COLORS = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#6d3d7e'];
const LABELS = ['A','B','C','D','E'];
let pts = [
  { x: 0.25, y: 0.30 },
  { x: 0.70, y: 0.20 },
  { x: 0.55, y: 0.65 },
  { x: 0.20, y: 0.75 },
  { x: 0.80, y: 0.80 }
];
/* Current projection angle (radians from positive x-axis) */
let dirAngle = Math.random() * Math.PI;
let dragging = null;

function toCanvas(p) { return { x: p.x * W, y: p.y * H }; }
function toNorm(cx, cy) { return { x: cx / W, y: cy / H }; }

/* Euclidean distance in pixel coordinates */
function dist2D(a, b) {
  const dx = (a.x - b.x) * W, dy = (a.y - b.y) * H;
  return Math.sqrt(dx * dx + dy * dy);
}
/* 1D projection: dot product with the random unit vector */
function project1D(p) {
  return (p.x * W) * Math.cos(dirAngle) + (p.y * H) * Math.sin(dirAngle);
}

/* Main render: grid, direction arrow, shadow projections, labeled dots */
function draw() {
  CTX.clearRect(0, 0, W, H);
  /* Light background grid */
  CTX.strokeStyle = '#dce3ea';
  CTX.lineWidth = 1;
  for (let i = 0; i <= 10; i++) {
    CTX.beginPath(); CTX.moveTo(i * W / 10, 0); CTX.lineTo(i * W / 10, H); CTX.stroke();
    CTX.beginPath(); CTX.moveTo(0, i * H / 10); CTX.lineTo(W, i * H / 10); CTX.stroke();
  }
  /* Green dashed direction arrow */
  const cx = W / 2, cy = H / 2;
  const ex = cx + Math.cos(dirAngle) * 110, ey = cy + Math.sin(dirAngle) * 110;
  const bx = cx - Math.cos(dirAngle) * 110, by = cy - Math.sin(dirAngle) * 110;
  CTX.strokeStyle = '#2a9d8f';
  CTX.lineWidth = 2;
  CTX.setLineDash([5, 4]);
  CTX.beginPath(); CTX.moveTo(bx, by); CTX.lineTo(ex, ey); CTX.stroke();
  CTX.setLineDash([]);
  CTX.fillStyle = '#2a9d8f';
  const a2 = dirAngle;
  CTX.beginPath();
  CTX.moveTo(ex, ey);
  CTX.lineTo(ex - 10 * Math.cos(a2 - 0.4), ey - 10 * Math.sin(a2 - 0.4));
  CTX.lineTo(ex - 10 * Math.cos(a2 + 0.4), ey - 10 * Math.sin(a2 + 0.4));
  CTX.closePath(); CTX.fill();

  /* Dashed lines from each point to its 1D shadow on the axis */
  pts.forEach((p, i) => {
    const proj = project1D(p);
    const sx = cx + Math.cos(dirAngle) * (proj - project1D({ x: 0.5, y: 0.5 }));
    const sy = cy + Math.sin(dirAngle) * (proj - project1D({ x: 0.5, y: 0.5 }));
    const cp = toCanvas(p);
    CTX.strokeStyle = COLORS[i] + '66';
    CTX.lineWidth = 1;
    CTX.beginPath(); CTX.moveTo(cp.x, cp.y); CTX.lineTo(sx, sy); CTX.stroke();
    CTX.fillStyle = COLORS[i] + '55';
    CTX.beginPath(); CTX.arc(sx, sy, 5, 0, Math.PI * 2); CTX.fill();
  });

  /* Colored labeled dots for each point */
  pts.forEach((p, i) => {
    const cp = toCanvas(p);
    CTX.fillStyle = COLORS[i];
    CTX.beginPath(); CTX.arc(cp.x, cp.y, 9, 0, Math.PI * 2); CTX.fill();
    CTX.fillStyle = '#fff';
    CTX.font = 'bold 11px system-ui';
    CTX.textAlign = 'center';
    CTX.textBaseline = 'middle';
    CTX.fillText(LABELS[i], cp.x, cp.y);
  });

  drawProjBar();
  updateTable();
}

/* Draw the 1D projection bar showing where each point maps */
function drawProjBar() {
  PCTX.clearRect(0, 0, PROJ.width, PROJ.height);
  PCTX.fillStyle = '#eef1f5';
  PCTX.fillRect(0, 0, PROJ.width, PROJ.height);
  const vals = pts.map(p => project1D(p));
  const mn = Math.min(...vals), mx = Math.max(...vals);
  const pad = 20;
  const range = mx - mn || 1;
  function toBar(v) { return pad + (v - mn) / range * (PROJ.width - 2 * pad); }
  PCTX.strokeStyle = '#adb5bd';
  PCTX.lineWidth = 1;
  PCTX.beginPath(); PCTX.moveTo(pad, 20); PCTX.lineTo(PROJ.width - pad, 20); PCTX.stroke();
  vals.forEach((v, i) => {
    const x = toBar(v);
    PCTX.fillStyle = COLORS[i];
    PCTX.beginPath(); PCTX.arc(x, 20, 7, 0, Math.PI * 2); PCTX.fill();
    PCTX.fillStyle = '#fff';
    PCTX.font = 'bold 9px system-ui';
    PCTX.textAlign = 'center';
    PCTX.textBaseline = 'middle';
    PCTX.fillText(LABELS[i], x, 20);
  });
}

/* Compute pairwise distances and distortion ratios, update table */
function updateTable() {
  const body = document.getElementById('dist-body');
  body.innerHTML = '';
  let maxDistortion = 0;
  for (let i = 0; i < pts.length; i++) {
    for (let j = i + 1; j < pts.length; j++) {
      const d = dist2D(pts[i], pts[j]);
      const pd = Math.abs(project1D(pts[i]) - project1D(pts[j]));
      const ratio = d > 0.001 ? pd / d : 1;
      maxDistortion = Math.max(maxDistortion, Math.abs(ratio - 1));
      const tr = document.createElement('tr');
      const ratioClass = Math.abs(ratio - 1) > 0.4 ? 'ratio-warn' : 'ratio-ok';
      tr.innerHTML = `<td>${LABELS[i]}–${LABELS[j]}</td><td>${d.toFixed(1)}</td><td>${pd.toFixed(1)}</td><td class="${ratioClass}">${ratio.toFixed(2)}</td>`;
      body.appendChild(tr);
    }
  }
  const s = document.getElementById('status');
  if (maxDistortion < 0.25) {
    s.textContent = i18nFmt('Max distortion %pct%% — this direction preserves distances well.', { pct: Math.round(maxDistortion * 100) });
    s.className = 'status ok';
  } else {
    s.textContent = i18nFmt('Max distortion %pct%% — try a new direction to reduce distortion.', { pct: Math.round(maxDistortion * 100) });
    s.className = 'status bad';
  }
}

/* Mouse drag handler: find the nearest point and move it */
function nearestPoint(cx, cy) {
  let best = -1, bestD = 16;
  pts.forEach((p, i) => {
    const cp = toCanvas(p);
    const d = Math.hypot(cp.x - cx, cp.y - cy);
    if (d < bestD) { bestD = d; best = i; }
  });
  return best;
}
CVS.addEventListener('mousedown', e => {
  const r = CVS.getBoundingClientRect();
  const cx = e.clientX - r.left, cy = e.clientY - r.top;
  dragging = nearestPoint(cx, cy);
});
CVS.addEventListener('mousemove', e => {
  if (dragging === null) return;
  const r = CVS.getBoundingClientRect();
  pts[dragging] = toNorm(e.clientX - r.left, e.clientY - r.top);
  pts[dragging].x = Math.max(0.03, Math.min(0.97, pts[dragging].x));
  pts[dragging].y = Math.max(0.03, Math.min(0.97, pts[dragging].y));
  draw();
});
CVS.addEventListener('mouseup', () => { dragging = null; });
CVS.addEventListener('mouseleave', () => { dragging = null; });

/* Touch drag support for mobile devices */
CVS.addEventListener('touchstart', e => {
  e.preventDefault();
  const r = CVS.getBoundingClientRect();
  const t = e.touches[0];
  dragging = nearestPoint(t.clientX - r.left, t.clientY - r.top);
}, { passive: false });
CVS.addEventListener('touchmove', e => {
  e.preventDefault();
  if (dragging === null) return;
  const r = CVS.getBoundingClientRect();
  const t = e.touches[0];
  pts[dragging] = toNorm(t.clientX - r.left, t.clientY - r.top);
  pts[dragging].x = Math.max(0.03, Math.min(0.97, pts[dragging].x));
  pts[dragging].y = Math.max(0.03, Math.min(0.97, pts[dragging].y));
  draw();
}, { passive: false });
CVS.addEventListener('touchend', () => { dragging = null; });

document.getElementById('btn-new').addEventListener('click', () => {
  dirAngle = Math.random() * Math.PI;
  draw();
});
document.getElementById('btn-reset').addEventListener('click', () => {
  pts = [
    { x: 0.25, y: 0.30 },
    { x: 0.70, y: 0.20 },
    { x: 0.55, y: 0.65 },
    { x: 0.20, y: 0.75 },
    { x: 0.80, y: 0.80 }
  ];
  dirAngle = Math.random() * Math.PI;
  draw();
});

draw();

<!-- Random Projection (JL Lemma) interactive demo -->
<p class="hint">Drag any colored point to move it. The green dashed line is the random projection direction. The bar below shows where each point lands on that axis. Watch the distortion ratios in the table.</p>
<div class="canvas-wrap">
  <canvas id="cvs" width="300" height="300" title="2D point canvas — drag points to reposition"></canvas>
</div>
<div class="proj-bar-wrap">
  <div class="proj-label">Projected positions (1D):</div>
  <canvas id="proj" width="300" height="40" title="1D projection bar"></canvas>
</div>
<div class="table-wrap">
  <table id="dist-table">
    <thead>
      <tr>
        <th>Pair</th>
        <th>Orig. dist.</th>
        <th>Proj. dist.</th>
        <th>Ratio</th>
      </tr>
    </thead>
    <tbody id="dist-body"></tbody>
  </table>
</div>
<div class="btns">
  <button id="btn-new" type="button">New random direction</button>
  <button id="btn-reset" type="button" class="ghost">Reset points</button>
</div>
<div class="status" id="status"></div>

/* Base layout and typography */
* { 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; }
/* Projection bar 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; }
/* Distance 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; }
/* Button and status 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Johnson–Lindenstrauss demo: 5 points in 2D, projected to 1D along a random unit vector. */
/* The ratio pd/d measures how much a single projection distorts each pairwise distance. */

const CVS = document.getElementById('cvs');
const CTX = CVS.getContext('2d');
const PROJ = document.getElementById('proj');
const PCTX = PROJ.getContext('2d');
const W = CVS.width, H = CVS.height;

/* Five labeled points in normalized [0,1]^2 coordinates */
const COLORS = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#6d3d7e'];
const LABELS = ['A','B','C','D','E'];
let pts = [
  { x: 0.25, y: 0.30 },
  { x: 0.70, y: 0.20 },
  { x: 0.55, y: 0.65 },
  { x: 0.20, y: 0.75 },
  { x: 0.80, y: 0.80 }
];
/* Current projection angle (radians from positive x-axis) */
let dirAngle = Math.random() * Math.PI;
let dragging = null;

function toCanvas(p) { return { x: p.x * W, y: p.y * H }; }
function toNorm(cx, cy) { return { x: cx / W, y: cy / H }; }

/* Euclidean distance in pixel coordinates */
function dist2D(a, b) {
  const dx = (a.x - b.x) * W, dy = (a.y - b.y) * H;
  return Math.sqrt(dx * dx + dy * dy);
}
/* 1D projection: dot product with the random unit vector */
function project1D(p) {
  return (p.x * W) * Math.cos(dirAngle) + (p.y * H) * Math.sin(dirAngle);
}

/* Main render: grid, direction arrow, shadow projections, labeled dots */
function draw() {
  CTX.clearRect(0, 0, W, H);
  /* Light background grid */
  CTX.strokeStyle = '#dce3ea';
  CTX.lineWidth = 1;
  for (let i = 0; i <= 10; i++) {
    CTX.beginPath(); CTX.moveTo(i * W / 10, 0); CTX.lineTo(i * W / 10, H); CTX.stroke();
    CTX.beginPath(); CTX.moveTo(0, i * H / 10); CTX.lineTo(W, i * H / 10); CTX.stroke();
  }
  /* Green dashed direction arrow */
  const cx = W / 2, cy = H / 2;
  const ex = cx + Math.cos(dirAngle) * 110, ey = cy + Math.sin(dirAngle) * 110;
  const bx = cx - Math.cos(dirAngle) * 110, by = cy - Math.sin(dirAngle) * 110;
  CTX.strokeStyle = '#2a9d8f';
  CTX.lineWidth = 2;
  CTX.setLineDash([5, 4]);
  CTX.beginPath(); CTX.moveTo(bx, by); CTX.lineTo(ex, ey); CTX.stroke();
  CTX.setLineDash([]);
  CTX.fillStyle = '#2a9d8f';
  const a2 = dirAngle;
  CTX.beginPath();
  CTX.moveTo(ex, ey);
  CTX.lineTo(ex - 10 * Math.cos(a2 - 0.4), ey - 10 * Math.sin(a2 - 0.4));
  CTX.lineTo(ex - 10 * Math.cos(a2 + 0.4), ey - 10 * Math.sin(a2 + 0.4));
  CTX.closePath(); CTX.fill();

  /* Dashed lines from each point to its 1D shadow on the axis */
  pts.forEach((p, i) => {
    const proj = project1D(p);
    const sx = cx + Math.cos(dirAngle) * (proj - project1D({ x: 0.5, y: 0.5 }));
    const sy = cy + Math.sin(dirAngle) * (proj - project1D({ x: 0.5, y: 0.5 }));
    const cp = toCanvas(p);
    CTX.strokeStyle = COLORS[i] + '66';
    CTX.lineWidth = 1;
    CTX.beginPath(); CTX.moveTo(cp.x, cp.y); CTX.lineTo(sx, sy); CTX.stroke();
    CTX.fillStyle = COLORS[i] + '55';
    CTX.beginPath(); CTX.arc(sx, sy, 5, 0, Math.PI * 2); CTX.fill();
  });

  /* Colored labeled dots for each point */
  pts.forEach((p, i) => {
    const cp = toCanvas(p);
    CTX.fillStyle = COLORS[i];
    CTX.beginPath(); CTX.arc(cp.x, cp.y, 9, 0, Math.PI * 2); CTX.fill();
    CTX.fillStyle = '#fff';
    CTX.font = 'bold 11px system-ui';
    CTX.textAlign = 'center';
    CTX.textBaseline = 'middle';
    CTX.fillText(LABELS[i], cp.x, cp.y);
  });

  drawProjBar();
  updateTable();
}

/* Draw the 1D projection bar showing where each point maps */
function drawProjBar() {
  PCTX.clearRect(0, 0, PROJ.width, PROJ.height);
  PCTX.fillStyle = '#eef1f5';
  PCTX.fillRect(0, 0, PROJ.width, PROJ.height);
  const vals = pts.map(p => project1D(p));
  const mn = Math.min(...vals), mx = Math.max(...vals);
  const pad = 20;
  const range = mx - mn || 1;
  function toBar(v) { return pad + (v - mn) / range * (PROJ.width - 2 * pad); }
  PCTX.strokeStyle = '#adb5bd';
  PCTX.lineWidth = 1;
  PCTX.beginPath(); PCTX.moveTo(pad, 20); PCTX.lineTo(PROJ.width - pad, 20); PCTX.stroke();
  vals.forEach((v, i) => {
    const x = toBar(v);
    PCTX.fillStyle = COLORS[i];
    PCTX.beginPath(); PCTX.arc(x, 20, 7, 0, Math.PI * 2); PCTX.fill();
    PCTX.fillStyle = '#fff';
    PCTX.font = 'bold 9px system-ui';
    PCTX.textAlign = 'center';
    PCTX.textBaseline = 'middle';
    PCTX.fillText(LABELS[i], x, 20);
  });
}

/* Compute pairwise distances and distortion ratios, update table */
function updateTable() {
  const body = document.getElementById('dist-body');
  body.innerHTML = '';
  let maxDistortion = 0;
  for (let i = 0; i < pts.length; i++) {
    for (let j = i + 1; j < pts.length; j++) {
      const d = dist2D(pts[i], pts[j]);
      const pd = Math.abs(project1D(pts[i]) - project1D(pts[j]));
      const ratio = d > 0.001 ? pd / d : 1;
      maxDistortion = Math.max(maxDistortion, Math.abs(ratio - 1));
      const tr = document.createElement('tr');
      const ratioClass = Math.abs(ratio - 1) > 0.4 ? 'ratio-warn' : 'ratio-ok';
      tr.innerHTML = `<td>${LABELS[i]}–${LABELS[j]}</td><td>${d.toFixed(1)}</td><td>${pd.toFixed(1)}</td><td class="${ratioClass}">${ratio.toFixed(2)}</td>`;
      body.appendChild(tr);
    }
  }
  const s = document.getElementById('status');
  if (maxDistortion < 0.25) {
    s.textContent = i18nFmt('Max distortion %pct%% — this direction preserves distances well.', { pct: Math.round(maxDistortion * 100) });
    s.className = 'status ok';
  } else {
    s.textContent = i18nFmt('Max distortion %pct%% — try a new direction to reduce distortion.', { pct: Math.round(maxDistortion * 100) });
    s.className = 'status bad';
  }
}

/* Mouse drag handler: find the nearest point and move it */
function nearestPoint(cx, cy) {
  let best = -1, bestD = 16;
  pts.forEach((p, i) => {
    const cp = toCanvas(p);
    const d = Math.hypot(cp.x - cx, cp.y - cy);
    if (d < bestD) { bestD = d; best = i; }
  });
  return best;
}
CVS.addEventListener('mousedown', e => {
  const r = CVS.getBoundingClientRect();
  const cx = e.clientX - r.left, cy = e.clientY - r.top;
  dragging = nearestPoint(cx, cy);
});
CVS.addEventListener('mousemove', e => {
  if (dragging === null) return;
  const r = CVS.getBoundingClientRect();
  pts[dragging] = toNorm(e.clientX - r.left, e.clientY - r.top);
  pts[dragging].x = Math.max(0.03, Math.min(0.97, pts[dragging].x));
  pts[dragging].y = Math.max(0.03, Math.min(0.97, pts[dragging].y));
  draw();
});
CVS.addEventListener('mouseup', () => { dragging = null; });
CVS.addEventListener('mouseleave', () => { dragging = null; });

/* Touch drag support for mobile devices */
CVS.addEventListener('touchstart', e => {
  e.preventDefault();
  const r = CVS.getBoundingClientRect();
  const t = e.touches[0];
  dragging = nearestPoint(t.clientX - r.left, t.clientY - r.top);
}, { passive: false });
CVS.addEventListener('touchmove', e => {
  e.preventDefault();
  if (dragging === null) return;
  const r = CVS.getBoundingClientRect();
  const t = e.touches[0];
  pts[dragging] = toNorm(t.clientX - r.left, t.clientY - r.top);
  pts[dragging].x = Math.max(0.03, Math.min(0.97, pts[dragging].x));
  pts[dragging].y = Math.max(0.03, Math.min(0.97, pts[dragging].y));
  draw();
}, { passive: false });
CVS.addEventListener('touchend', () => { dragging = null; });

document.getElementById('btn-new').addEventListener('click', () => {
  dirAngle = Math.random() * Math.PI;
  draw();
});
document.getElementById('btn-reset').addEventListener('click', () => {
  pts = [
    { x: 0.25, y: 0.30 },
    { x: 0.70, y: 0.20 },
    { x: 0.55, y: 0.65 },
    { x: 0.20, y: 0.75 },
    { x: 0.80, y: 0.80 }
  ];
  dirAngle = Math.random() * Math.PI;
  draw();
});

draw();

Result

Console

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 Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/random-projection-jl/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Random Projection (JL)

How a random matrix preserves distances up to a tiny distortion