Optimal terminal dimensionality reduction in Euclidean space
Let $\varepsilon\in(0,1)$ and $X\subset\mathbb R^d$ be arbitrary with $|X|$ having size $n>1$. The Johnson-Lindenstrauss lemma states there exists $f:X\rightarrow\mathbb R^m$ with $m = O(\varepsilon^{-2}\log n)$ such that $$ \forall x\in X\ \forall y\in X, \|x-y\|_2 \le \|f(x)-f(y)\|_2 \le (1+\varepsilon)\|x-y\|_2 . $$ We show that a strictly stronger version of this statement holds, answering one of the main open questions of [MMMR18]: "$\forall y\in X$" in the above statement may be replaced with "$\forall y\in\mathbb 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(\varepsilon^{-4}\log n)$. Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of [MMMR18].
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionLEMMASimilar Papers 제목 키워드 기반
Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, …
Dimensionality ReductionDiversityOptimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used, not much is known in terms of bounds on …
Dimensionality ReductionnSimplex Zen: A Novel Dimensionality Reduction for Euclidean and Hilbert Spaces
Dimensionality reduction techniques map values from a high dimensional space to one with a lower dimension. The result is a space which requires less physical memory and has a faster distance calculation. These technique…
Dimensionality ReductionFibeRed: Fiberwise Dimensionality Reduction of Topologically Complex Data with Vector Bundles
Datasets with non-trivial large scale topology can be hard to embed in low-dimensional Euclidean space with existing dimensionality reduction algorithms. We propose to model topologically complex datasets using vector bu…
Dimensionality ReductionNeighbor Embeddings Using Unbalanced Optimal Transport Metrics
This paper proposes the use of the Hellinger--Kantorovich metric from unbalanced optimal transport (UOT) in a dimensionality reduction and learning (supervised and unsupervised) pipeline. The performance of UOT is compar…
Dimensionality Reduction