On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$

DOI10.1137/140977655zbMath1330.68294arXiv1308.4996OpenAlexW865313152MaRDI QIDQ5499733

Ofer Neiman, Lee-Ad J. Gottlieb, Yair Bartal

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

embeddingsdoubling dimensionLaakso graph

Mathematics Subject Classification ID

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

Related Items (2)

A doubling subset of \(L_p\) for \(p>2\) that is inherently infinite dimensional ⋮ No dimension reduction for doubling subsets of \(\ell_q\) when \(q>2\) revisited

Cites Work

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

This page was built for publication: On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$