2018/10/22 by Narayanan, Shyam, Nelson, Jelani
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.1810.09250
Let ε∈(0,1) and X⊂\mathbb Rd be arbitrary with |X| having size n>1. The Johnson-Lindenstrauss lemma states there exists f:X→\mathbb Rm with m = O(ε-2log n) such that ∀ x∈ X ∀ y∈ X, ‖x-y‖2 ≤ ‖f(x)-f(y)‖2 ≤ (1+ε)‖x-y‖2 . 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∈\mathbb Rd", 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(ε-4log n). Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of [MMMR18].