A lower bound on dimension reduction for trees in ℓ₁

2013/02/26 by James R. Lee, Mohammad Moharrami, Lee, James R. +1
Computer Science · Mathematics · #Advanced Mathematical Modeling in Engineering #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Analysis and Curvature Flows #Metric Geometry (math.MG) #Nonlinear Partial Differential Equations #cs.DM #math.MG

paper · pdf · doi:10.48550/arxiv.1302.6542

openalex publication_date 2013/02/26 · arxiv created 2013/02/27 · arxiv updated 2013/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

There is a constant c > 0 such that for every ε∈ (0,1) and n ≥ 1/ε², the following holds. Any mapping from the n-point star metric into ℓ₁^d with bi-Lipschitz distortion 1+ε requires dimension d ≥ clog n\over ε²log (1/ε).

Citations

• Entropy-based Bounds on Dimension Reduction in L₁

Related

• Dimension reduction for finite trees in L₁
• Entropy-based Bounds on Dimension Reduction in L₁
• On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ_p, p>2
• Embedding Probability Distributions into Low Dimensional ℓ₁: Tree Ising Models via Truncated Metrics
• Metric dimension reduction modulus for superlogarithmic distortion