On the impossibility of dimension reduction for doubling subsets of _p

DOI10.1137/140977655MaRDI QIDQ5499733zbMATH OpenOpenAlexFDO

Authors Ofer Neiman, Yair Bartal, Lee-Ad Gottlieb

Publication date 31 July 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

doubling dimensionembeddingsLaakso graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Applications of graph theory (05C90) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: A major open problem in the field of metric embedding is the existence of dimension reduction for $n$-point subsets of Euclidean space, such that both distortion and dimension depend only on the {em doubling constant} of the pointset, and not on its cardinality. In this paper, we negate this possibility for $el{l}_p$ spaces with $p>2$. In particular, we introduce an $n$-point subset of $el{l}_p$ with doubling constant O(1), and demonstrate that any embedding of the set into $el{l}_p^d$ with distortion $D$ must have $DgeOmegaleft(left(fracclogndight{)}^{frac12-frac1p}ight)$.

Recommendations

• On the impossibility of dimension reduction for doubling subsets of \(\ell_p\)
• No dimension reduction for doubling subsets of \(\ell_q\) when \(q>2\) revisited
• A nonlinear approach to dimension reduction
• A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional
• Ultra-low-dimensional embeddings for doubling metrics

Cites work

• A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional
• A lower bound on the distortion of embedding planar metrics into Euclidean space
• A nonlinear approach to dimension reduction
• A simple proof of the restricted isometry property for random matrices
• An algorithmic theory of learning: Robust concepts and random projection
• Approximation algorithm for the kinetic robust \(k\)-center problem
• Assouad's theorem with dimension independent of the snowflaking
• Bilipschitz embeddings of metric spaces into space forms
• Bilipschitz snowflakes and metrics of negative type
• Bypassing the embedding
• Compact routing with slack in low doubling dimension
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Deformable spanners and applications
• Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
• Distance estimation and object location via rings of neighbors
• Efficient Classification for Metric Data
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Entropy-based bounds on dimension reduction in L^1
• Extensions of Lipschitz mappings into a Hilbert space
• scientific article; zbMATH DE number 5764811 (Why is no real title available?)
• scientific article; zbMATH DE number 5764820 (Why is no real title available?)
• scientific article; zbMATH DE number 5764857 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1775451 (Why is no real title available?)
• scientific article; zbMATH DE number 2109363 (Why is no real title available?)
• scientific article; zbMATH DE number 6469222 (Why is no real title available?)
• Kernels as features: on kernels, margins, and low-dimensional mappings
• Low dimensional embeddings of doubling metrics
• Measured descent: A new embedding method for finite metrics
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Near Linear Lower Bound for Dimension Reduction in L1
• Near-optimal distortion bounds for embedding doubling spaces into L ₁
• On average distortion of embedding metrics into the line and into l₁
• On the impossibility of dimension reduction in l ₁
• On the nonexistence of bilipschitz parameterizations and geometric problems about \(A_ \infty\)-weights
• On the optimality of gluing over scales
• PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Problems and results in extremal combinatorics. I.
• Proximity algorithms for nearly doubling spaces
• Searching dynamic point sets in spaces with bounded doubling dimension
• Small hop-diameter sparse spanners for doubling metrics
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• The geometry of graphs and some of its algorithmic applications
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Triangulation and embedding using small sets of beacons
• Ultra-low-dimensional embeddings for doubling metrics
• Using the doubling dimension to analyze the generalization of learning algorithms

Cited in

(9)

• No dimension reduction for doubling subsets of \(\ell_q\) when \(q>2\) revisited
• Dimension reduction techniques for \(\ell_p\) \((1<p<2)\), with applications
• Metric dimension reduction: a snapshot of the Ribe program
• Dimension reduction for hyperbolic space
• On the impossibility of dimension reduction for doubling subsets of \(\ell_p\)
• A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional
• A nonlinear approach to dimension reduction
• Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1
• \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\)

This page was built for publication: On the impossibility of dimension reduction for doubling subsets of \(\ell_{p}\)

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