Friday, November 5, 2021 - 3:00pm to 4:00pm
Location:In Person and Virtual Presentation - ET Gates Hillman 8102 and Zoom
Speaker:JELANI NELSON, Professor http://people.eecs.berkeley.edu/~minilek/?_ga=2.69009492.472207941.1636140135-14...
Optimal terminal dimensionality reduction in Euclidean space
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". We also discuss some progress on construction of such a map f which can be computed quickly.
Based on works with Yeshwanth Cherapanamjeri, and with Shyam Narayanan.
In Person and Zoom Participation. See announcement.