Dimension reduction techniques for _p (1

DOI10.4230/LIPICS.SOCG.2016.16zbMATH Open1387.68236arXiv1408.1789OpenAlexW2490165199MaRDI QIDQ3132849FDOQ3132849

Authors: Yair Bartal, Lee-Ad Gottlieb 

Publication date: 30 January 2018

Abstract: For Euclidean space ($el{l}_2$), there exists the powerful dimension reduction transform of Johnson and Lindenstrauss, with a host of known applications. Here, we consider the problem of dimension reduction for all $el{l}_p$ spaces $1leple2$. Although strong lower bounds are known for dimension reduction in $el{l}_1$, Ostrovsky and Rabani successfully circumvented these by presenting an $el{l}_1$ embedding that maintains fidelity in only a bounded distance range, with applications to clustering and nearest neighbor search. However, their embedding techniques are specific to $el{l}_1$ and do not naturally extend to other norms. In this paper, we apply a range of advanced techniques and produce bounded range dimension reduction embeddings for all of $1leple2$, thereby demonstrating that the approach initiated by Ostrovsky and Rabani for $el{l}_1$ can be extended to a much more general framework. We also obtain improved bounds in terms of the intrinsic dimensionality. As a result we achieve improved bounds for proximity problems including snowflake embeddings and clustering.

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

Recommendations

• Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
• A nonlinear approach to dimension reduction
• On the impossibility of dimension reduction for doubling subsets of \(\ell_p\)
• On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)
• A nonlinear approach to dimension reduction

zbMATH Keywords

dimension reductionembeddings

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Geometry and structure of normed linear spaces (46B20) Banach sequence spaces (46B45)

Cited In (11)

• Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)
• Nonlinear Estimators and Tail Bounds for Dimension Reduction in l 1 Using Cauchy Random Projections
• Some remarks about dimension reduction for −Δ1
• Dimension reduction of multivariate linear systems under \(H^ \infty\) constraints
• Dimension reduction for hyperbolic space
• Tight embeddability of proper and stable metric spaces
• A nonlinear approach to dimension reduction
• Title not available (Why is that?)
• Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Title not available (Why is that?)

This page was built for publication: Dimension reduction techniques for \(\ell_p\) \((1<p<2)\), with applications

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