• Calendar

May 11, Tuesday
12:00 – 13:30

The celebrated Johnson-Lindenstrauss lemma says that every n points in Euclidean space can be represented with O(log n) dimensions with only a minor distortion of pairwise distances. It has been conjectured that a such-improved dimension reduction representation is achievable for many interesting data sets, by bounding the target dimension in terms of the intrinsic dimensions of the data (for example, by replacing the log n term with the doubling dimension). This question appears to be quite challenging, requiring new (nonlinear) embedding techniques. We make progress towards resolving this question by presenting two dimension reduction theorems with similar flavor to the conjecture. For some intended applications, these results can serve as an alternative to the conjectured embedding. [Joint work with Robert Krauthgamer.]