On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ_p, p>2

2013/08/22 by Yair Bartal, Bartal, Yair, Lee-Ad Gottlieb +3
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Digital Image Processing Techniques #FOS: Computer and information sciences #Mathematical Approximation and Integration #cs.CG

paper · pdf · doi:10.48550/arxiv.1308.4996

arxiv created 2013/08/22 · openalex publication_date 2013/08/22 · arxiv updated 2013/08/26 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

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 ℓ_p spaces with p>2. In particular, we introduce an n-point subset of ℓ_p with doubling constant O(1), and demonstrate that any embedding of the set into ℓ_p^d with distortion D must have D≥Ω(((clog n)/(d))^{(1)/(2)-(1)/(p)}).

Related

• No dimension reduction for doubling subsets of ℓ_q when q>2 revisited
• Entropy-based Bounds on Dimension Reduction in L₁
• A lower bound on dimension reduction for trees in ℓ₁
• Dimension reduction techniques for ℓ_p, 1 ≤ p ≤ 2, with applications
• An example of a doubling "inherently" infinite-dimensional subset of l₂