Linear Algebra

The lemma gives a probabilistic guarantee that distances between vectors can be preserved after projection into a lower-dimensional space.

Programming

Why Distances Matter

Many datasets represent each item as a vector with a large number of dimensions. Working with all of those dimensions can be expensive, so dimensionality reduction lowers the number of dimensions while preserving as much important information as possible. In the Johnson-Lindenstrauss setting, the important information is the distances between vectors in a finite set.

The Johnson-Lindenstrauss Lemma describes a way to project a finite collection of vectors from a high-dimensional Euclidean space into a lower-dimensional space. Its central guarantee is probabilistic: after projection, distances between the vectors can be preserved. The result does not claim that every possible vector in the entire space is preserved; its setup concerns a finite vector set.

What happens to the distances between vectors when a finite set moves from a high-dimensional space into a lower-dimensional space?

The Projection Setup

The lemma starts with a finite vector set Q in R^{^d}. The symbol d represents the original number of coordinates, so R^{^d} is the original, possibly high-dimensional, space. The target space has dimension n, where n is an integer satisfying the condition required by the lemma.

The projection is performed with a random matrix W in R^{^n,d}. The target dimension is represented by n, while d represents the original dimension. Each entry of W is normally distributed with zero mean and variance 1/n. Multiplying the vectors by this matrix produces their projected representations in the lower-dimensional setting.

How are the finite vector set, original dimension, target dimension, probability parameter, and random matrix connected?

Symbol	Role
Q	Finite set of vectors
d	Original dimension
n	Target, lower dimension
δ	Probability parameter in the lemma's guarantee
W	Random projection matrix in R^{^n,d}

The main objects in the projection setup

Reading the Guarantee

The phrase probabilistic guarantee means that the distance-preservation statement is expressed with a probability parameter rather than as an unconditional statement. The finite set Q, the lower dimension n, the parameter δ, and the random matrix W all belong to the lemma's setup. The guarantee concerns the distances between vectors in Q after the projection.

When interpreting a probability bound in this context, identify two separate ideas. First, the projection changes the representation by moving vectors into a lower-dimensional space. Second, the lemma gives a probability-qualified statement about how well distances between the finite collection of vectors are preserved. The parameter δ is the probability parameter used to express that qualification.

How do the projection result and the probability parameter fit together in the Johnson-Lindenstrauss statement?

Vectors as Column Objects

In this chapter, vectors are column vectors in finite-dimensional Euclidean spaces. Their coordinates are arranged vertically rather than across a row. A vector with d coordinates belongs to R^{^d}; the symbol d records the number of coordinates.

text

u = (2, −1, 3)ᵀ

u = (2, −1, 3)ᵀ

The superscript T is a compact way to display the coordinate list as a column-vector representation. The important convention is that u is one vertical vector with three coordinates, not three unrelated values.

For two vectors u and v in R^{^d}, the inner product is commonly written as ⟨u, v⟩. It connects the two vectors. When the same vector appears twice, ⟨u, u⟩ is the inner product of that vector with itself.

Three Measurements of One Vector

The same vector can be measured in different ways. The Euclidean norm, also called the ℓ2 norm, combines squared coordinate magnitudes and takes a square root. It is obtained from the inner product of the vector with itself. The ℓ1 norm totals coordinate magnitudes. The ℓ∞ norm keeps only the largest coordinate magnitude.

Formula

Rule

How does each norm measure a different feature of the same vector, and how does the Euclidean norm use the inner product with itself?

Worked Norm Calculation

Worked example

Measuring u = (2, −1, 3)

Calculate the inner product of u with itself, then use it to calculate the Euclidean norm. Also calculate the ℓ1 and ℓ∞ norms.

1
Self inner product
Multiply corresponding coordinates and add: ⟨u, u⟩ = 2² + (−1)² + 3² = 4 + 1 + 9 = 14.
2
Euclidean norm
Use the inner product with itself: ||u||₂ = √⟨u, u⟩ = √14.
3
ℓ1 norm
Add the coordinate magnitudes: ||u||₁ = |2| + |−1| + |3| = 2 + 1 + 3 = 6.
4
ℓ∞ norm
Keep the largest coordinate magnitude: ||u||∞ = max(2, 1, 3) = 3.

Result

For u = (2, −1, 3), the self inner product is 14, the Euclidean norm is √14, the ℓ1 norm is 6, and the ℓ∞ norm is 3.

Measurement	What it uses	Value for u
⟨u, u⟩	Squared coordinate magnitudes without the final square root	14
ℓ2 norm	Square root of the self inner product	√14
ℓ1 norm	All coordinate magnitudes added together	6
ℓ∞ norm	Largest coordinate magnitude	3

Different rules measure different features of the same vector

Common Interpretation Errors

Common mistake
Treating dimensionality reduction as if it preserved every detail of every vector.
What it looks like
Assuming that projecting into R^n leaves all information unchanged.
Why it fails
The lemma focuses on preserving distances between vectors in a finite set, not on claiming that every detail or every vector in the whole space is unchanged.
Do this instead
State the result in terms of distance preservation for the finite set Q and its probabilistic guarantee.
Common mistake
Confusing d with n.
What it looks like
Calling n the original dimension and d the target dimension.
Why it fails
d represents the original dimension, while n represents the target lower dimension.
Do this instead
Read W in R^(n,d) with n as the target dimension and d as the original dimension.
Common mistake
Forgetting that W is random.
What it looks like
Describing W as an arbitrary fixed matrix without mentioning how its entries are sampled.
Why it fails
The projection uses a random matrix whose entries are normally distributed with zero mean and variance 1/n.
Do this instead
Identify W as the random matrix used for projection and include its stated entry distribution.
Common mistake
Using the ℓ1 norm when the question asks for the Euclidean norm.
What it looks like
Reporting 6 as the Euclidean norm of (2, −1, 3).
Why it fails
Six is the sum of coordinate magnitudes, which is the ℓ1 norm.
Do this instead
For the Euclidean norm, take the square root of the vector's inner product with itself, giving √14 for this vector.
Common mistake
Using a coordinate value instead of its magnitude for the ℓ∞ norm.
What it looks like
Choosing −1 as the largest coordinate because it is numerically negative.
Why it fails
The ℓ∞ norm keeps the largest coordinate magnitude.
Do this instead
Compare absolute values and choose the largest magnitude; for (2, −1, 3), the result is 3.

Practice Check

EASY

Let v = (−2, 4, 1). Calculate ⟨v, v⟩, ||v||₂, ||v||₁, and ||v||∞. Then state which norm uses the largest coordinate magnitude and which norm totals all coordinate magnitudes.

Hints

For the self inner product, square each coordinate and add the results.
For the Euclidean norm, take the square root of the self inner product.
For the ℓ1 norm, add 2, 4, and 1.
For the ℓ∞ norm, choose the largest magnitude.

Your attempt (not saved)

MEDIUM

In your own words, explain the roles of Q, d, n, δ, and W in the Johnson-Lindenstrauss setup. Be precise about which dimension is original and which is the target.