Linear Algebra

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.

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.

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.

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.

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.

||u||₂ = √⟨u, u⟩

||u||₁ = sum of the coordinate magnitudes

||u||∞ = largest coordinate magnitude

Worked Norm Calculation

Common Interpretation Errors

• Treating dimensionality reduction as if it preserved every detail of every vector.

  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.

  Fix: State the result in terms of distance preservation for the finite set Q and its probabilistic guarantee.

• Confusing d with n.

  d represents the original dimension, while n represents the target lower dimension.

  Fix: Read W in R^(n,d) with n as the target dimension and d as the original dimension.

• Forgetting that W is random.

  The projection uses a random matrix whose entries are normally distributed with zero mean and variance 1/n.

  Fix: Identify W as the random matrix used for projection and include its stated entry distribution.

• Using the ℓ1 norm when the question asks for the Euclidean norm.

  Six is the sum of coordinate magnitudes, which is the ℓ1 norm.

  Fix: For the Euclidean norm, take the square root of the vector's inner product with itself, giving √14 for this vector.

• Using a coordinate value instead of its magnitude for the ℓ∞ norm.

  The ℓ∞ norm keeps the largest coordinate magnitude.

  Fix: Compare absolute values and choose the largest magnitude; for (2, −1, 3), the result is 3.

Practice Check

Key Takeaways

1. The Johnson-Lindenstrauss Lemma gives a probabilistic guarantee that distances within a finite vector set can be preserved after projection into a lower-dimensional space.
2. The setup uses a finite set Q in R^d, a target dimension n, a probability parameter δ, and a random matrix W in R^(n,d).
3. Vectors in this chapter are column vectors in finite-dimensional Euclidean spaces.
4. The Euclidean norm is obtained by taking the square root of a vector's inner product with itself.
5. The ℓ1 norm totals coordinate magnitudes, while the ℓ∞ norm keeps the largest coordinate magnitude.