"Optimal terminal dimensionality reduction in Euclidean space"
Jelani Nelson (UC Berkeley)
Monday, April 27th 2-3pm
Zoom Meeting: https://ucsd.zoom.us/my/csetheoryseminar, password "theory"
Abstract: The Johnson-Lindenstrauss lemma states that for any X a subset of R^d with |X| = n and for any epsilon, there exists a map f:X-->R^m for m = O(log n / epsilon^2) such that: for all x in X, for all y in X, (1-epsilon)|x - y|_2 <= |f(x) - f(y)|_2 <= (1+epsilon)|x - y|_2 We show that this statement can be strengthened. In particular, the above claim holds true even if "for all y in X" is replaced with "for all y in R^d". Joint work with Shyam Narayanan.