3. Vorlesung: Random projections and the Johnson-Lindenstrauss embedding

Random projections

• Definition
• How can we construct random projections
• Some of their mathematical properties

The Johnson-Lindenstrauss Lemma

• The Theorem
• The proof
• Applications

High-dimensional vs. low-dimensional spaces: what are properties, advantages, and disadvantages of high-dimensional spaces?

Literature:

On both random projections and Johnson-Lindenstrauss: Start with DasguptaGupta99 (they prove the Johnson-Lindenstrauss theorem the way we did in the lecture). Achlioptas03 considers the simpler random projections with the binary random matrices. LinialLondonRabinovich95 show how random projections in general can be applied to various problems in computer science. Kleinberg97 discusses random projections to find approximate nearest neighbors.

On high dimensional spaces: JimenezLandgrebe98 and Flaschka02

Demos:

• what can happen in high-dimensional spaces: demo_highdim_spaces.m
• random projections: demo_random_projection.m

Puzzles and exercises:

• On the one hand we have seen that if we project data on a random vector, it often looks like a normal distribution. On the other hand, the Johnson-Lindenstrauss Lemma tells us that distances are nearly preserved in random projections. How can this be?
• In the lecture I explained that by drawing an iid sample X_1,...,X_d from a normal distribution and normalizing the vector (X_1,...,X_d) we can produce a uniform distribution on the sphere in R^d. Prove this statement formally.
• How can we implement a random projection on a k-dim subspace?
• In the lecture I proved that the expected squared length of the projection of a fixed vector x on a random vector v is 1/d. Prove that the expected squared length of a projection of a fixed vector on a random k-dim subspace is k/d.