Dimension reduction techniques for _p (1

DOI10.4230/LIPICS.SOCG.2016.16MaRDI QIDQ3132849zbMATHOpenAlexFDO

Authors Yair Bartal, Lee-Ad Gottlieb

Publication date 30 January 2018

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

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)

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.

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

Cited in

(12)

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

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)