Optimal terminal dimensionality reduction in Euclidean space

DOI10.1145/3313276.3316307MaRDI QIDQ5212846zbMATH OpenOpenAlexFDO

Authors Shyam Narayanan, Jelani Nelson

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.09250

zbMATH Keywords

dimension reductionrandom projectionsterminal embeddings

Mathematics Subject Classification ID

Metric embeddings as related to computational problems and algorithms (68R12) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Let $varepsilonin(0,1)$ and $Xsubsetmathbb{R}^d$ be arbitrary with $|X|$ having size $n>1$. The Johnson-Lindenstrauss lemma states there exists $f:Xightarrowmathbb{R}^m$ with $m=O(varepsilo{n}^{-2}logn)$ such that ${\displaystyle }$ forall xin X forall yin X, |x-y|_2 le |f(x)-f(y)|_2 le (1+varepsilon)|x-y|_2 . ${\displaystyle }$ We show that a strictly stronger version of this statement holds, answering one of the main open questions of [MMMR18]: "$forallyinX$" in the above statement may be replaced with "$forallyinmathbb{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(varepsilo{n}^{-4}logn)$. Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of [MMMR18].

Recommendations

• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• Dimensionality reductions in \(\ell_{2}\) that preserve volumes and distance to affine spaces
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Near Optimal Dimensionality Reductions That Preserve Volumes
• Generalizing the Johnson--Lindenstrauss lemma to \(k\)-dimensional affine subspaces

Cited in

(23)

• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• Dimensionality reduction for \(k\)-distance applied to persistent homology
• Near isometric terminal embeddings for doubling metrics
• Embeddings of surfaces, curves, and moving points in Euclidean space
• Embeddings of surfaces, curves, and moving points in euclidean space
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Optimal (Euclidean) Metric Compression
• Lossless prioritized embeddings
• On the fixed-parameter tractability of capacitated clustering
• Nonlinear dimension reduction via outer bi-Lipschitz extensions
• Labelings vs. embeddings: on distributed and prioritized representations of distances
• Approximation schemes for k-facility location
• Optimality of the Johnson-Lindenstrauss dimensionality reduction for practical measures
• Terminal embeddings in sublinear time
• On outer bi-Lipschitz extensions of linear Johnson-Lindenstrauss embeddings of subsets of \(\mathbb{R}^N\)
• Approximate nearest neighbor for curves -- simple, efficient, and deterministic
• Space complexity of Euclidean clustering
• Dimension-independent kernel -covers
• Random projections for curves in high dimensions
• An empirical evaluation of k-means coresets
• On the budgeted priority p-median problem in high-dimensional Euclidean spaces
• Parameterized approximation schemes for fair-range clustering

This page was built for publication: Optimal terminal dimensionality reduction in Euclidean space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212846)