skip to content

In random projection, what sets the target dimension for a 100,000-column feature matrix?

level: seniorimportance: should knowfreq 33%

answer

  1. the lemma counts points, not columns
  2. no fitting pass at all
  3. tolerance enters squared
  4. log n over epsilon squared
  5. worst-case constant, verify empirically

basics

~20 s

The Johnson-Lindenstrauss bound sets it from the number of points and the distortion you accept, roughly log(n) divided by epsilon squared. The original 100,000 columns do not appear in the bound at all, and the bound itself is conservative.

solid answer

~50 s

Random projection multiplies the data by a matrix drawn at random — Gaussian entries, or scaled plus-or-minus-one entries — with no fitting step at all. The Johnson-Lindenstrauss lemma says that for any set of n points, a target dimension on the order of `log(n) / eps^2` is enough for every pairwise distance to survive within a factor of `1 +/- eps`. Two consequences matter in an interview. First, the width of the input does not enter: 100,000 hashed columns and 5,000 columns need the same target dimension for the same n and eps. Second, the dependence is quadratic in eps, so tightening the tolerance from 0.2 to 0.1 roughly quadruples the target, while ten times more points costs only a log factor. The bound is a worst-case guarantee with a loose constant, so in practice you pick something like 512 and verify empirically that the downstream metric holds.

code

python · 22 lines
python
import random, math

random.seed(0)
d, k = 2000, 128
a = [random.gauss(0, 1) for _ in range(d)]
b = [random.gauss(0, 1) for _ in range(d)]

# The matrix is drawn without looking at the data.
scale = 1.0 / math.sqrt(k)
R = [[random.choice((-scale, scale)) for _ in range(d)] for _ in range(k)]

def project(v):
    return [sum(row[i] * v[i] for i in range(d)) for row in R]

def dist(u, v):
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(u, v)))

before = dist(a, b)
after = dist(project(a), project(b))
print("before:", round(before, 3))
print("after: ", round(after, 3))
print("relative distortion:", round(abs(after - before) / before, 3))

go deeper

for a junior

Be ready to say that the projection matrix is random, is never fitted on the data, and keeps distances between points roughly the same while making the data much narrower.

for a middle

Explain the shape of the bound: dimension grows with the log of the point count and with one over the tolerance squared, and does not depend on the original width. Know the plus-or-minus-one matrix variant.

for a senior

Show operational judgment — pick a target empirically against a downstream metric rather than from the formula, version the seed with the model, and know that dense random matrices destroy input sparsity.

for a principal

Own the tradeoff against a fitted projection at the platform level: a fixed random map decouples retrains and keeps every worker consistent, at the cost of extra width and total loss of feature interpretability.

## The mechanism A random projection replaces a d-column matrix with a k-column one by multiplying it by a k-by-d matrix whose entries are drawn at random and never looked at again. A common choice is independent Gaussian entries scaled by `1/sqrt(k)`; a database-friendly alternative uses entries of `+1/sqrt(k)` and `-1/sqrt(k)`, optionally with most entries set to zero for sparsity. The critical property is that the matrix is drawn **without seeing the data**. There is no covariance to estimate, no eigen-decomposition, no fitting pass. The same matrix can be generated from a stored random seed on any machine and applied to rows that arrive later in a stream. ## What the lemma guarantees The Johnson-Lindenstrauss lemma states that for any set of n points in any number of dimensions and any tolerance eps between 0 and 1, there is a linear map into k dimensions, with k on the order of `log(n) / eps^2`, such that every pairwise distance is preserved within a factor of `1 +/- eps`. The standard sufficient bound has the shape `k >= (4 * ln n) / (eps^2 / 2 - eps^3 / 3)`. A random matrix satisfies it with high probability, which is why the lemma is constructive in practice: draw one and you almost certainly have a good map. Read the bound carefully, because the interview turns on what is *not* in it: - **n, the number of points, is in it — logarithmically.** Ten times more rows raises the requirement by roughly `ln 10`, a small additive amount, not a factor of ten. - **eps is in it — quadratically.** Halving the distortion you tolerate multiplies the required dimension by about four. This is the term that dominates cost. - **d, the original width, is absent.** A hashed feature matrix with 100,000 columns needs the same target dimension as a 5,000-column one, for the same point count and tolerance. This is the counter-intuitive part and the reason random projection is attractive for very wide, very sparse data. ## The bound is a guarantee, not a recipe The constants in the lemma are worst-case: they must hold for the most adversarial point configuration imaginable. Plugging a large n and a tight eps into the formula often returns a target dimension larger than the input you were trying to shrink, which is a signal that you are reading the bound as a prescription instead of as an existence guarantee. Real data has structure, so the distortion you actually observe is usually far smaller than the worst case. Practitioners choose a target like 256 or 512, project, and then measure what they care about — retrieval recall against the exact result, a validation metric of the downstream model, or the empirical distribution of distance ratios on a sample of pairs. Treat the bound as the shape of the tradeoff (log in points, quadratic in tolerance, free in width) and treat the specific number as an empirical question. ## What you give up compared with a fitted projection A fitted projection like a variance-maximising or supervised one looks at the data and spends each output dimension on a direction the data actually uses; a random projection spends dimensions blindly. For the same fidelity, random projection therefore usually needs more output dimensions. What you buy is: - **No fitting cost.** No pass over the data to estimate structure, and no decomposition whose cost grows with the width or the sample count. - **Streaming and distributed safety.** Every worker generates the identical matrix from a shared seed; new data needs no refit, and the meaning of the output columns never drifts because the matrix never changes. - **Stability across retrains.** Refitting a data-dependent projection silently changes what every output column means, forcing everything downstream to retrain. A fixed random matrix has no such coupling. What you also give up is interpretability: an output column is a random blend of thousands of inputs and corresponds to nothing a human can name. Distances are approximately preserved, but individual coordinate values are meaningless, so any downstream logic must depend on geometry alone. ## Operational notes Store the seed, not the matrix, and version it beside the model — a projection you cannot reproduce makes an old model unusable. Apply the projection after whatever scaling you use, since the distance guarantee is about the space you actually project. And remember the guarantee is about **pairwise distances**, not about angles to a fixed reference, not about preserving sparsity (a dense Gaussian matrix destroys sparsity; the sparse plus-or-minus-one variants exist partly to mitigate this), and not about any per-feature semantics.

  • Why does halving the distortion tolerance cost roughly four times the dimensions?
    Because the tolerance enters the bound as `eps^2` in the denominator. Going from eps = 0.2 to eps = 0.1 divides the denominator by about four, so the required target dimension multiplies by about four. Point count, by contrast, enters logarithmically, so ten times more rows costs only a small additive increase. Tolerance, not scale, is what makes random projection expensive.
  • How does the cost profile differ from a projection that is fitted on the data?
    A fitted projection needs a pass over the data and a decomposition before it can produce a single output, and refitting it changes the meaning of every output column, forcing downstream retraining. A random matrix costs one seeded draw and a matrix multiply, works on streaming rows, and is identical across workers. The price is fidelity: you generally need more output dimensions for the same distance quality.
  • Must the projection matrix have Gaussian entries?
    No. Entries of plus or minus one over the square root of k give comparable distance-preservation guarantees, and sparse variants that zero out most entries do too, which makes the multiply much cheaper on sparse input. What matters is that the entries are independent, zero-mean and correctly scaled, not that they are Gaussian.
  • What should you store so a projected model stays reproducible?
    The random seed and the generation scheme, versioned alongside the model, plus the target dimension and any scaling applied before the projection. Storing a 100,000-by-512 matrix is wasteful and easy to lose; a seed reconstructs it exactly. A model whose projection cannot be regenerated is a model that cannot score new data.

Casting a shadow from a randomly chosen angle. Any single shadow distorts a little, but for a whole crowd of points almost every angle keeps who-is-near-whom roughly intact.

saying these in an interview costs you the question

  • Says the target dimension scales with the number of input columns
  • Treats the Johnson-Lindenstrauss bound as tight rather than worst-case
  • Thinks the random matrix is fitted on the training data
  • Claims distances are preserved exactly rather than approximately
  • Expects individual projected columns to keep a feature meaning
  • Forgets to version the seed, so the projection cannot be reproduced

context

resolving links…