Optimal terminal dimensionality reduction in Euclidean space

Abstract

Let (0,1) and X R^d be arbitrary with |X| having size n>1. The Johnson-Lindenstrauss lemma states there exists f:X R^m with m = O(^-2 n) such that We show that a strictly stronger version of this statement holds, answering one of the main open questions of [MMMR18]: " y X" in the above statement may be replaced with " y R^d", so that f not only preserves distances within X, but also distances to X from the rest of space. Previously this stronger version was only known with the worse bound m = O(^-4 n). Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of [MMMR18].

Tasks

Reproductions