Jelani Nelson: The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

Abstract: For any n>1 and eps in (0,1/2), we show the existence of a
poly(n) sized subset X of R^n such that any linear map from (X, l_2)
to l_2^m with distortion 1+eps must have a target dimension satisfying
m = Omega( min{ n, eps^{-2} log n } ). The proof is simple, and all
details will fit in the talk. Our lower bound matches the upper bounds
provided by the identity matrix and the Johnson-Lindenstrauss lemma,
and is thus optimal. Previously, Alon proved a bound against all
embeddings (not necessarily linear), but which was worse by a
log(1/eps) factor. I will close the talk with evidence of why I believe
it might be possible to beat the JL lemma using non-linear maps.

Joint work with Kasper Green Larsen.