Nonlinear dimension reduction via outer bi-Lipschitz extensions

DOI10.1145/3188745.3188828MaRDI QIDQ5230364zbMATH OpenOpenAlexFDO

Authors Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn

Publication date 22 August 2019

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

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

zbMATH Keywords

bi-Lipschitz extensiondimension reductionmetric embeddingnear-isometric mapsprioritized Johnson-Lindenstrauss

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a Lipschitz map. We show that for every map $f$ there exists an outer bi-Lipschitz extension $f^{\prime }$ whose distortion is greater than that of $f$ by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems. * We prove a prioritized variant of the Johnson-Lindenstrauss lemma: given a set of points $Xsubsetmathbb{R}^d$ of size $N$ and a permutation ("priority ranking") of $X$, there exists an embedding $f$ of $X$ into $mathbb{R}^{O(logN)}$ with distortion $O(loglogN)$ such that the point of rank $j$ has only $O(lo{g}^{3+varepsilon}j)$ non-zero coordinates - more specifically, all but the first $O(lo{g}^{3+varepsilon}j)$ coordinates are equal to $0$; the distortion of $f$ restricted to the first $j$ points (according to the ranking) is at most $O(loglogj)$. The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions. * We prove that given a set $X$ of $N$ points in $mathbb{R}^d$, there exists a terminal dimension reduction embedding of $mathbb{R}^d$ into $mathbb{R}^{d^{\prime }}$, where $d^{\prime }=Oleft(fraclogNvarepsilo{n}^{4}ight)$, which preserves distances $|x-y|$ between points $xinX$ and $yinmathbb{R}^d$, up to a multiplicative factor of $1pmvarepsilon$. This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.

Recommendations

• Optimal terminal dimensionality reduction in Euclidean space
• Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
• Lossless prioritized embeddings
• A simple proof of the Johnson-Lindenstrauss extension theorem
• A nonlinear approach to dimension reduction

Cited in

(16)

• Dimensionality reduction for \(k\)-distance applied to persistent homology
• Near isometric terminal embeddings for doubling metrics
• On Lipschitz inversion of nonlinear redundant representations
• Optimal (Euclidean) Metric Compression
• Lossless prioritized embeddings
• On the fixed-parameter tractability of capacitated clustering
• Terminal embeddings in sublinear time
• Efficient Kirszbraun extension with applications to regression
• On outer bi-Lipschitz extensions of linear Johnson-Lindenstrauss embeddings of subsets of \(\mathbb{R}^N\)
• A normalized bottleneck distance on persistence diagrams and homology preservation under dimension reduction
• Approximate nearest neighbor for curves -- simple, efficient, and deterministic
• Clustering under a knapsack constraint: parameterized approximation for the knapsack median problem
• Information preservation with Wasserstein autoencoders: generation consistency and adversarial robustness
• An empirical evaluation of k-means coresets
• Clustering with a knapsack constraint: parameterized approximation algorithms for the knapsack median problem
• Two-sided Kirszbraun theorem

This page was built for publication: Nonlinear dimension reduction via outer bi-Lipschitz extensions

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