Terminal Embeddings in Sublinear Time
share
Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a terminal embedding from one metric space (X,d_X) to another (Y,d_Y) with a set of designated terminals T⊂ X. Such an embedding f is said to have distortion ρ≥ 1 if ρ is the smallest value such that there exists a constant C>0 satisfying ∀ x∈ T ∀ q∈ X, C d_X(x, q) ≤ d_Y(f(x), f(q)) ≤ C ρ d_X(x, q) . In the case that X,Y are both Euclidean metrics with Y being m-dimensional, recently (Narayanan, Nelson 2019), following work of (Mahabadi, Makarychev, Makarychev, Razenshteyn 2018), showed that distortion 1+ϵ is achievable via such a terminal embedding with m = O(ϵ^-2log n) for n := |T|. This generalizes the Johnson-Lindenstrauss lemma, which only preserves distances within T and not to T from the rest of space. The downside is that evaluating the embedding on some q∈ℝ^d required solving a semidefinite program with Θ(n) constraints in m variables and thus required some superlinear poly(n) runtime. Our main contribution in this work is to give a new data structure for computing terminal embeddings. We show how to pre-process T to obtain an almost linear-space data structure that supports computing the terminal embedding image of any q∈ℝ^d in sublinear time O^* (n^1-Θ(ϵ^2) + d). To accomplish this, we leverage tools developed in the context of approximate nearest neighbor search.
READ FULL TEXT