Mathematical Sciences Research Institute

Home » Workshop » Schedules » Optimality of the Johnson-Lindenstrauss lemma

Optimality of the Johnson-Lindenstrauss lemma

Geometric functional analysis and applications November 13, 2017 - November 17, 2017

November 16, 2017 (11:00 AM PST - 12:00 PM PST)
Speaker(s): Jelani Nelson (Harvard University)
Location: MSRI: Simons Auditorium
  • metric embeddings

  • Johnson-Lindenstrauss lemma

  • dimensionality reduction

Primary Mathematics Subject Classification
Secondary Mathematics Subject Classification No Secondary AMS MSC



Dimensionality reduction in Euclidean space, as attainable by the Johnson-Lindenstrauss lemma, has been a fundamental tool in algorithm design and machine learning. The JL lemma states that any n point subset of l_2 can be mapped to l_2^m with distortion 1+epsilon, where m = O(epsilon^{-2} log n). In this talk, I discuss our recent proof that the JL lemma is optimal, in the sense that for any n, d, epsilon, where epsilon is not too small, there is a point set X in l_2^d such that any f:X->l_2^m with 1+epsilon must have m = Omega(epsilon^{-2} log n). I will also discuss some subsequent work and future directions. Joint work with Kasper Green Larhus (Aarhus University).

30100?type=thumb Nelson Notes 3.83 MB application/pdf Download
Video/Audio Files


H.264 Video 13-Nelson.mp4 161 MB video/mp4 rtsp://videos.msri.org/data/000/030/022/original/13-Nelson.mp4 Download
Troubles with video?

Please report video problems to itsupport@msri.org.

See more of our Streaming videos on our main VMath Videos page.