No dimension reduction for doubling subsets of ℓ_q when q>2 revisited

2021/03/08 by Florent P. Baudier, Baudier, Florent P., Krzysztof Święcicki +3
Computer Science · Engineering · Mathematics · #05C63 #46B20 #46B85 #46B99 #51F30 #68R12 #Coding theory and cryptography #FOS: Mathematics #Limits and Structures in Graph Theory #Metric Geometry (math.MG) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2103.05080

openalex publication_date 2021/03/08 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28

Abstract

We revisit the main results from \citesBGN_SoCG14,BGN_SIAM15 and \citeLafforgueNaor14_GD about the impossibility of dimension reduction for doubling subsets of ℓ_q for q>2. We provide an alternative elementary proof of this impossibility result that combines the simplicity of the construction in \citesBGN_SoCG14,BGN_SIAM15 with the generality of the approach in \citeLafforgueNaor14_GD (except for L₁ targets). One advantage of this different approach is that it can be naturally generalized to obtain embeddability obstructions into non-positively curved spaces or asymptotically uniformly convex Banach spaces.

Related

• On the Impossibility of Dimension Reduction for Doubling Subsets of ℓ_p, p>2
• An example of a doubling "inherently" infinite-dimensional subset of l₂
• A doubling subset of L_p for p>2 that is inherently infinite dimensional
• Dimension reduction techniques for ℓ_p, 1 ≤ p ≤ 2, with applications
• Entropy-based Bounds on Dimension Reduction in L₁