Preserving Geometry with Fewer Coordinates
A map can omit most details of a city yet preserve what a traveller needs: which places are near, which are far, and roughly how distances compare. Dimensionality reduction asks for an analogous map of data. A point with a million coordinates is replaced by one with far fewer coordinates while selected geometric relationships remain approximately true.
Consider three points in two dimensions: $a=(1,0)$, $b=(0,1)$, and $c=(1,1)$. Their squared distances are $\lVert a-b\rVert_2^2=2$ and $\lVert a-c\rVert_2^2=\lVert b-c\rVert_2^2=1$. Mapping every point to its first coordinate sends $a$ and $c$ to the same value, destroying one distance. A random projection does not promise perfection, but with enough target dimensions it makes such large distortions unlikely for a fixed finite set.
The Johnson–Lindenstrauss idea is striking because the required target dimension depends logarithmically on the number of points, not directly on the original dimension. Gaussian and Rademacher matrices provide dense random projections; sparse JL and feature hashing reduce update cost; fast JL transforms mix coordinates before subsampling; subspace embeddings preserve every vector in a low-dimensional linear subspace rather than merely a fixed list of points.
The boundary matters. An embedding preserves the geometry named in its theorem—usually Euclidean norms or distances, with stated probability and distortion. It does not automatically preserve labels, fairness, rare semantic features, nearest-neighbor identity when margins are tiny, or arbitrary future points chosen after seeing the map.
Dimensionality reduction trades exact coordinates for approximate geometric relationships. A small target dimension is justified only relative to a finite point set or structured subspace, a distortion budget, and a failure probability—not for every vector in the original space simultaneously.
| Concept | Intuitive meaning | Exact example | Non-example or boundary | Assumption | Question answered |
|---|---|---|---|---|---|
| Distortion | Relative change in length or distance | Squared distance $10$ mapped into $[9,11]$ has $10\%$ distortion | Additive error one means different things at distances $1$ and $100$ | Original distance is nonzero for a ratio | How faithfully is geometry retained? |
| JL embedding | Random map preserving all pairwise distances in a fixed finite set | $N$ points mapped to $k=O(\varepsilon^{-2}\log(N/\delta))$ dimensions | One map preserving every vector in $\mathbb R^n$ when $k\lt n$ | Set is fixed independently of the random map | Can finite Euclidean geometry be compressed? |
| Gaussian projection | Dense matrix with scaled independent normal entries | $R_{ij}\sim N(0,1/k)$ | Unscaled normals, whose expected norm grows with $k$ | Independent subgaussian rows | What simple map supports concentration? |
| Rademacher projection | Dense random signs with scale $1/\sqrt{k}$ | $R_{ij}\in\{-1,+1\}/\sqrt{k}$ | Deterministic repeated sign rows | Sufficient independence and scaling | Can simpler randomness replace Gaussians? |
| Sparse JL / feature hashing | Each input coordinate touches few output coordinates | One signed bucket per feature in hashing | Collision-free preservation for every input | Sparsity and input-coherence conditions of the theorem | How can projection cost be reduced? |
| Subspace embedding | Preserve every vector in one $d$-dimensional subspace | Norms of all $Ax$ preserved for every $x$ | Preserving only the matrix columns separately | Oblivious map independent of the fixed subspace | Can regression and low-rank geometry be compressed? |
Preserving Geometry with Fewer Coordinates
Use points $a=(1,0)$, $b=(0,1)$, and $c=(1,1)$.
- Compute squared pairwise distances: $d^2(a,b)=2$, $d^2(a,c)=1$, and $d^2(b,c)=1$.
- Project onto the first coordinate with $P(x_1,x_2)=x_1$. The images are $1,0,1$, so the $a,c$ distance collapses from $1$ to $0$.
- Project onto the unit direction $u=(1,1)/\sqrt2$. The images are $1/\sqrt2,1/\sqrt2,\sqrt2$. Now $a,b$ collapse instead.
- Neither one-dimensional map can preserve all three distances well. This is consistent with JL: it promises a sufficient target dimension depending on distortion and set size, not that $k=1$ always works.
Reflection: a projection may preserve most distances but collapse the particular pair that determines a nearest-neighbor decision. What additional margin condition would make approximate distances sufficient to preserve that decision?
Distances, Projections and Distortion
For a linear map $R:\mathbb R^n\to\mathbb R^k$, norm preservation for a vector $v$ means
$$ (1-\varepsilon)\lVert v\rVert_2^2\le\lVert Rv\rVert_2^2\le(1+\varepsilon)\lVert v\rVert_2^2. $$
Distance preservation for points $x_i,x_j$ follows by applying the norm statement to $v=x_i-x_j$. A fixed-vector guarantee quantifies over one vector chosen independently of $R$. A finite-set JL guarantee applies a tail bound to all pairwise differences and uses a union bound. A subspace embedding is stronger: with high probability, the inequality holds simultaneously for every vector in a fixed $d$-dimensional subspace.
For a Gaussian matrix with entries $N(0,1/k)$ and fixed $v$, rotational symmetry gives $\lVert Rv\rVert_2^2/\lVert v\rVert_2^2$ distributed like $\chi_k^2/k$. Its expectation is one, and concentration gives a failure probability exponentially small in $k\varepsilon^2$ for $0\lt\varepsilon\lt1$. Rademacher projections obtain comparable concentration using independent scaled signs.
For $N$ fixed points, there are fewer than $N^2/2$ pairwise differences. Making the per-difference failure probability roughly $\delta/N^2$ yields target dimension $k=O(\varepsilon^{-2}(\log N+\log(1/\delta)))$, with constant and lower-order dependence determined by the chosen tail inequality.
Sparse JL uses fewer nonzeros per column to accelerate multiplying sparse inputs, but extreme input concentration can increase collisions unless the construction and sparsity meet the relevant theorem. Feature hashing is an especially sparse signed map: each feature hashes to a bucket with a random sign. FJLT first randomizes signs and applies a fast orthogonal mixing transform, then samples or projects fewer coordinates, spreading a concentrated vector before reduction.
flowchart TD
A[Choose fixed data object] --> B{What must be preserved?}
B -->|One vector| C[Fixed-vector norm]
B -->|N points| D[All pairwise differences]
B -->|d-dimensional subspace| E[All vectors in the subspace]
C --> F[Random projection expectation]
F --> G[Concentration around norm one]
D --> H[Apply fixed-vector tail to fewer than N squared pairs]
H --> I[Union bound]
E --> J[Net argument or matrix concentration]
G --> K[Choose k from epsilon and delta]
I --> L[Choose k from epsilon, delta, and log N]
J --> M[Choose k from epsilon, delta, and d]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B navy;
class C,D,E teal;
class F,H,J purple;
class G,I,K,L,M crimson;
| Definition or result | Exact scope | Required assumptions | What it does not imply | Counterexample or consequence |
|---|---|---|---|---|
| Fixed-vector JL tail | One fixed $v$ has its squared norm preserved with high probability | $v$ independent of the random map and correctly scaled randomness | Simultaneous preservation of uncountably many vectors | After seeing $R$, choose a nonzero vector in its null space |
| Finite-set JL | All pairwise distances among $N$ fixed points are preserved | Union bound over fixed differences | Exact nearest-neighbor identity without a margin | Two candidates with almost equal distances may swap order |
| Gaussian projection | Dense subgaussian map with isotropic rows | Independent $N(0,1/k)$ entries | Fast multiplication for huge sparse inputs | Dense matrix touches every input coordinate-output pair |
| Rademacher projection | Similar norm concentration using scaled signs | Adequate independence and $1/\sqrt{k}$ scaling | Deterministic signs with the same guarantee | Repeated rows can annihilate a structured vector |
| Feature hashing | Very sparse signed projection | Random hash/signs and appropriate input/model conditions | Worst-case preservation for every vector at arbitrarily small $k$ | Two large features collide with opposite signs and cancel |
| FJLT | Fast mixing plus sampling/projection | Fast orthogonal transform, random signs, suitable dimensions | Universally faster for every sparse or hardware setting | Padding and dense mixing may dominate small problems |
| Subspace embedding | Simultaneously preserves all vectors in a fixed $d$-dimensional subspace | Map independent of the subspace and target dimension sized for $d$ | Preserving all of $\mathbb R^n$ with $k\lt n$ | A vector outside the subspace may lie in the null space |
JL preserves pairwise distance by preserving norms of difference vectors. The probability statement is over the random map for a fixed set chosen independently of it; choosing a bad vector after inspecting a dimension-reducing map defeats any claim about all of $\mathbb R^n$.
Why Random Embeddings Work
Take a fixed nonzero vector $v$ and a Gaussian projection $R\in\mathbb R^{k\times n}$ with entries $N(0,1/k)$. Each row dot product is normal with variance $\lVert v\rVert_2^2/k$. Therefore
$$ \frac{\lVert Rv\rVert_2^2}{\lVert v\rVert_2^2}=\frac1k\sum_{r=1}^k Z_r^2, $$
where the $Z_r$ are independent standard normals. The mean is one. A chi-square tail bound shows deviations beyond $\varepsilon$ occur with probability at most roughly $2e^{-c k\varepsilon^2}$ for $0\lt\varepsilon\lt1$ and an absolute constant $c$.
For $N$ points, apply this to every difference $x_i-x_j$. There are at most $N(N-1)/2$ pairs. The union bound does not require pairwise failure events to be independent; it simply adds their probabilities. Choosing $k$ large enough that each failure probability is at most about $2\delta/N^2$ makes the probability of any distorted pair at most $\delta$.
The logarithm appears when solving an exponential tail for $k$: $e^{-c k\varepsilon^2}$ must beat a polynomial number of pairs. Reducing distortion by half is expensive because $k$ scales quadratically with $1/\varepsilon$. Increasing the dataset size multiplicatively only adds to $\log N$.
This proof fails if the set is selected adaptively after $R$ is exposed. When $k\lt n$, $R$ has a nonzero null-space vector $v$ with $Rv=0$, causing total distortion. It also fails if rows are unscaled or strongly dependent, because isotropy or concentration can disappear. Sparse transforms need their own analysis; copying the dense proof without checking collision structure is not valid.
flowchart TD
A[Fix nonzero vector v independently of R] --> B[Scale random rows so expected projected energy equals original energy]
B --> C[Express projected norm as average of independent squared variables]
C --> D[Apply chi-square or subgaussian concentration]
D --> E[Fixed-vector failure decays exponentially in k epsilon squared]
E --> F[Replace v by every pairwise difference]
F --> G[At most N squared over two bad events]
G --> H[Union bound total failure by delta]
H --> I[Solve for k proportional to epsilon inverse squared times log N over delta]
A -. choose v after seeing R .-> X[Null-space counterexample]
B -. wrong scale or dependence .-> Y[Expectation or concentration fails]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B navy;
class C,D,E purple;
class F,G,H,I teal;
class X,Y crimson;
Why Random Embeddings Work
Suppose a particular JL tail bound guarantees that a fixed vector fails with probability at most $2e^{-k\varepsilon^2/8}$. You have $N=100$ fixed points, want $\varepsilon=0.25$, and require total failure at most $\delta=0.01$.
- There are $M=N(N-1)/2=4{,}950$ pairwise differences.
- Require $2M e^{-k\varepsilon^2/8}\le\delta$.
- Rearranging gives $k\ge(8/\varepsilon^2)\ln(2M/\delta)$.
- Here $8/0.0625=128$ and $\ln(990{,}000)\approx13.81$, so this conservative bound gives $k\ge1{,}768$.
- The result exceeds the original dimension in many small examples. A sufficient worst-case bound can be conservative; projection is useful only if the actual $n$, workload, constants, and empirical behavior justify it.
Assumption-breaking variation: generate a random $R$ with $k\lt n$, inspect it, and then choose nonzero $v\in\ker(R)$. The projected norm is zero. Identify exactly which “fixed independently of $R$” quantifier the construction violates.
| Proof tool or viewpoint | What it establishes | Assumptions | Tightness or limitation | Failure case |
|---|---|---|---|---|
| Isotropy / expectation | $\mathbb E\lVert Rv\rVert_2^2=\lVert v\rVert_2^2$ | Correct scaling and second moments | Mean preservation alone permits large variance | One row receives nearly all projected energy |
| Chi-square concentration | Exponential fixed-vector tail for Gaussian maps | Independent Gaussian rows | Specific to dense Gaussian structure | Correlated duplicate rows reduce effective sample size |
| Subgaussian concentration | Comparable tails for signs and other light-tailed maps | Independence or suitable limited independence and subgaussian control | Constants and randomness differ by construction | Heavy-tailed entries create frequent large distortions |
| Union bound | Simultaneous finite-set guarantee | Fixed finite event family; independence not required | Can be conservative | Treating an uncountable sphere as finitely many points without a net |
| Epsilon-net argument | Extends finite control to a fixed subspace sphere | Covering-number argument plus operator control | Introduces dimension and constant overhead | Net result applied without controlling points between the net |
| Preconditioning / mixing | Reduces coordinate concentration before sparse sampling | Random signs and an orthogonal fast transform | Extra passes and hardware costs | Omitting mixing on a basis vector before coordinate sampling |
| Empirical distortion audit | Measures workload-specific quality | Representative fixed evaluation pairs | No universal guarantee under drift or adaptivity | Test set excludes rare high-coherence vectors |
Nearest Neighbors and Compressed Features
For a small image collection, projection can compress embedding vectors before approximate nearest-neighbor search. If distances are preserved within $1\pm\varepsilon$, a neighbor with a clear margin over the runner-up usually remains preferred. With almost tied candidates, even a theorem-compliant distortion can reverse the order, so recall must be measured at the actual margin distribution.
In text or advertising systems, feature hashing maps millions of sparse categorical features into a smaller vector. Signed hashing reduces systematic collision bias in inner products, but collisions can erase rare high-value features. The feature dictionary, hash seed, normalization, and target dimension become model-versioned production artifacts.
For least squares and randomized linear algebra, a subspace embedding compresses the rows of a design matrix while preserving norms in its column space. Solving the smaller problem can approximate the original objective. This is a different quantifier from finite-point JL: every vector in the column space must be preserved.
Misleading cases include data selected after the map is published, distribution drift toward highly coherent vectors, and protected or rare groups whose decision margins are smaller. An embedding can satisfy a global geometric metric while harming a critical slice. Random projection preserves mathematical distance; it does not certify that the upstream embedding or metric represents the desired semantics.
Nearest Neighbors and Compressed Features: Dimensionality Reduction
A learner stores four two-dimensional feature vectors: query $q=(1,1)$ and candidates $a=(1,2)$, $b=(3,1)$, $c=(-1,-1)$. Their squared distances from $q$ are $1$, $4$, and $8$.
Use the one-dimensional signed projection $R=(1,1)/\sqrt2$. Images are $Rq=\sqrt2$, $Ra=3/\sqrt2$, $Rb=4/\sqrt2$, and $Rc=-\sqrt2$. Projected squared distances are $1/2$, $2$, and $8$; every value is exactly half its original because these particular difference vectors have components aligned in a favorable way. If we rescale this one-row map by $\sqrt2$, these three query distances become exact.
Now add $d=(2,0)$. Its original squared distance from $q$ is $2$, but $Rd=Rq$, so the projected distance is zero. The same map is not uniformly reliable even for this tiny expanded set.
Model-selection conclusion: use the example to understand linear projection, not to justify $k=1$. For a real fixed collection, select $k$ from a distortion/failure budget and validate all relevant query-candidate pairs.
Success criteria: reproduce all distances, identify the collapsed difference $(1,-1)$ as orthogonal to $R$, and state a measurable acceptance rule such as $99\%$ recall@10 with p99 relative distance distortion below the chosen bound.
Nearest Neighbors and Compressed Features: Dimensionality Reduction
A retrieval platform stores $N=50$ million normalized embeddings of dimension $n=4{,}096$. It targets recall@20 of at least $98\%$, p99 query latency below 80 ms, projected storage below 30% of the original, and no critical language slice below $96\%$ recall.
Design: compare dense Rademacher, sparse JL, and a fast transform at target dimensions $k\in\{256,384,512,768\}$. Version the normalization, seed, map family, and $k$. Search projected vectors to generate a larger candidate set, then rerank candidates with original-vector distance. Keep queries and corpus fixed independently of each evaluation seed.
Evidence: empirical distortion distributions on random pairs and hard-neighbor pairs; recall versus neighbor margin; slice metrics; storage, projection throughput, index-build cost, and latency; seed-to-seed variability; drift after embedding-model releases; collision/coherence stress tests; and adaptive-query red-team results.
Risks: a global average hides rare slices, feature normalization changes the geometry, sparse inputs can collide under feature hashing, and users may adapt queries after deployment. Exact reranking protects precision among retrieved candidates but cannot recover a true neighbor omitted during projected search.
Decision: choose the smallest $k$ whose confidence bounds meet every recall and slice target under the memory/latency budget. Trigger rollback or dual-index migration if margin-adjusted recall or distortion drifts beyond its control limit; do not infer safety from the asymptotic JL order alone.
Choose Dimensions from a Distortion Budget
Target dimension is a contract, not a magic constant. Identify the set or subspace, Euclidean geometry, acceptable multiplicative distortion, global failure probability, and downstream margin. Then choose a theorem appropriate to the transform, calculate a conservative $k$, and measure whether constants and workload structure permit a smaller operational value.
Practice: Choose Dimensions from a Distortion Budget
Assume a fixed-vector bound $2e^{-k\varepsilon^2/8}$ and a fixed set of $N=10{,}000$ points. Require all pairwise squared distances to have distortion at most $\varepsilon=0.2$ with total failure probability at most $\delta=10^{-3}$.
Tier 1 — Definitions. Define fixed-vector norm preservation, finite-set JL, feature hashing, FJLT, and subspace embedding. State the quantifiers for each. Checkpoint: distinguish a fixed point set from inputs chosen after the map.
Tier 2 — Dimension derivation. With at most $N^2/2$ pairs, solve $N^2e^{-k\varepsilon^2/8}\le\delta$. Obtain $k\ge(8/\varepsilon^2)\ln(N^2/\delta)$. Substitute the values: $8/0.04=200$ and $\ln(10^{11})\approx25.33$, yielding the conservative sufficient bound $k\ge5{,}066$. Record that exact constants depend on the selected theorem.
Tier 3 — Proof roadmap. Explain isotropy, concentration for one fixed difference, the union bound over pairs, and why logarithm and $\varepsilon^{-2}$ appear. Independence between pairwise bad events is not needed.
Tier 4 — Counterexamples. Give (a) an unscaled projection, (b) duplicate random rows, (c) a vector chosen from the map’s null space after inspection, and (d) two nearly tied neighbors whose order can reverse within the allowed distortion.
Tier 5 — Transform choice. Compare Gaussian, Rademacher, sparse JL/feature hashing, and FJLT for a dense batch matrix and for single sparse online vectors. Include multiplication cost, memory, randomness, hardware fit, and theorem assumptions.
Tier 6 — Professional artifact. Produce a dimension-selection memo with $N$ or subspace dimension $d$, $n$, $\varepsilon$, $\delta$, theorem and constants, calculated $k$, candidate operational values, seed policy, distance and recall metrics, slice analysis, drift monitoring, exact-verification stage, and rollback rule.
Debugging prompts: if norms inflate with $k$, check scaling; if basis vectors collapse, inspect sparse collisions; if offline results vary across runs, version seeds; if recall falls despite acceptable average distortion, inspect neighbor margins and tail pairs; if post-launch queries degrade, examine adaptivity and drift.
Stretch goal: derive how $k$ changes when $N$ grows tenfold, $\delta$ decreases one hundredfold, or $\varepsilon$ halves. Explain why halving $\varepsilon$ is typically the most expensive of these changes.
Rubric (10 points): definitions and quantifiers 2; correct dimension derivation 2; proof logic 2; valid counterexamples 2; measurable production decision 2. Full credit requires separating theorem-level squared-norm distortion from downstream nearest-neighbor recall.
Decision checklist: name the fixed set or subspace, metric, distortion, failure budget, transform family, scaling, randomness, and downstream margin; calculate $k$ from the matching theorem; then validate tail pairs, slices, speed, and drift. Expectation is not concentration, fixed-vector success is not all-vector success, and exact reranking cannot restore missed candidates. These embeddings connect linear sketches to randomized linear algebra, least squares, low-rank approximation, and large-scale graph and matrix processing.
Next in the Series
In Randomized Numerical Linear Algebra, we'll explore Sketch matrices for regression, low rank, and spectral tasks..