Euclidean Distance
Random projections transform a vector using a random matrix.
Why Distance Matters
Dimensionality reduction replaces a vector with a description that has fewer dimensions. The challenge is to make that description smaller without losing too much of the structure we care about. For Euclidean-distance problems, that structure includes how far vectors are from one another. Random projections address this challenge by applying a random linear transformation and accepting a controlled amount of distance distortion.
The goal is not to preserve every Euclidean distance exactly. The goal is to reduce dimension while limiting how much relevant distances change.
From Vector to Projection
A random projection starts with a vector and a randomly selected matrix. Multiplying the matrix by the vector produces a new vector that represents the original using fewer dimensions. The transformation is random because the matrix is selected without designing a separate transformation specifically around each input.
Tracing one projection
Suppose a vector has many coordinates and a randomly selected matrix has fewer rows than the vector has coordinates. What role does the multiplication play?
Start with the vector: The original vector is the high-dimensional object to be represented more compactly.
Select the matrix: A random matrix is selected rather than a transformation designed specifically for this input.
Multiply: Matrix-vector multiplication combines the original coordinates according to the matrix and produces the projected vector.
Use the projection: The projected vector is a lower-dimensional description. Its usefulness depends on how much of the relevant distance structure remains.
The random matrix turns the original vector into a lower-dimensional projected vector through a random linear transformation.
Controlled Distance Change
Projection can change Euclidean distances because the vectors are being represented in fewer dimensions. Random projections are valuable when that change is limited rather than arbitrary. This is the central trade-off: the representation becomes smaller, while the distances used to describe relationships between vectors remain sufficiently controlled.
The Johnson-Lindenstrauss Idea
The Johnson-Lindenstrauss Lemma gives a formal bound on the distortion introduced by a random projection. Its central idea is that many points can be represented in fewer dimensions while their pairwise Euclidean distances are approximately preserved, rather than changed without control.
Read the lemma as a distortion guarantee. It supports the claim that dimension can be reduced while relevant pairwise distances undergo controlled change; it does not claim exact equality of all distances.
Sparsity in Compressed Sensing
Compressed sensing approaches dimensionality reduction from a different starting point. It assumes that a vector is sparse in some basis. Sparse means that most entries are zero, or that only a small number of entries are nonzero. The source describes a vector x in R d with at most s nonzero elements. Compressed sensing uses this prior knowledge instead of treating every coordinate as equally significant.
Recognizing the compressed-sensing assumption
Consider two vectors with the same number of coordinates. One has only a small number of nonzero entries in a particular basis, while the other does not. Which one matches the key prior assumption of compressed sensing?
Inspect the basis: Sparsity is not stated independently of representation. The vector must be considered in some basis.
Count nonzero elements: The relevant vector has at most a small number of nonzero elements; most of its entries are zero.
Apply the assumption: That sparse structure is the information compressed sensing takes advantage of.
The vector that is sparse in the relevant basis matches the compressed-sensing assumption.
Two Routes to Reduction
Random projections and compressed sensing share a broad goal: replace a vector or collection of vectors with a description using fewer dimensions. Their assumptions differ. Random projections use a random linear transformation and rely on limiting Euclidean-distance distortion. Compressed sensing uses prior knowledge that a vector has at most a small number of nonzero elements in some basis.
| Method | Main transformation or information | Key assumption | What is controlled or exploited |
|---|---|---|---|
| Random projections | Random linear transformation using a random matrix | A lower-dimensional representation can limit distance distortion | Euclidean distances change in a controlled way |
| Compressed sensing | A compressed description based on a sparse representation | The vector has at most a small number of nonzero elements in some basis | Sparsity is exploited |
Treating a random projection as exact distance preservation.
The value of random projections comes from limiting distortion, not eliminating it.
Fix:
Describe the result as approximate distance preservation with controlled change.Describing compressed sensing as merely another random projection.
Compressed sensing uses the prior assumption that a vector is sparse in some basis.
Fix:
State the sparsity assumption and explain that only a small number of entries are nonzero.Ignoring the basis when discussing sparsity.
The source defines the assumption as sparsity in some basis.
Fix:
Connect the sparsity claim to the relevant basis.Assuming both methods use the same reason for compression.
Random projections use a random linear transformation and distance control; compressed sensing exploits sparsity.
Fix:
Separate the shared goal from the different assumptions.
Check Your Understanding
A method multiplies a vector by a randomly selected matrix and produces a representation with fewer dimensions. Explain why this method can still be useful even though the Euclidean distances may change. Then contrast its assumption with the assumption used by compressed sensing.
Hints
- Mention controlled or limited distortion rather than exact preservation.
- For compressed sensing, identify what must be true about the vector in some basis.
What do you think happens?
A learner says, 'The Johnson-Lindenstrauss Lemma means random projection keeps every Euclidean distance exactly unchanged.' Is that statement correct?
Reveal answer
Answer: No, the guarantee concerns bounded or controlled distortion.
The lemma gives a formal bound on distortion. Random projection is useful because distances can change in a limited way, not because every distance remains exactly the same.
Essential Takeaways
- A random projection multiplies a vector by a randomly selected matrix to create a lower-dimensional representation.
- Its usefulness comes from limiting Euclidean-distance distortion rather than preserving every distance exactly.
- The Johnson-Lindenstrauss Lemma gives a formal bound on the distortion introduced by random projection.
- Compressed sensing uses a different assumption: the vector has at most a small number of nonzero elements in some basis.
- Random projections and compressed sensing share a dimensionality-reduction goal but rely on different information.
Key Takeaways
- Random matrices create random projections by transforming vectors into fewer dimensions.
- The important property is controlled Euclidean-distance distortion, not exact preservation.
- The Johnson-Lindenstrauss Lemma formalizes the idea that distances can remain approximately preserved after dimension reduction.
- Compressed sensing relies on sparsity in some basis rather than primarily on distance preservation.
- Both approaches reduce dimensionality, but their assumptions and purposes differ.