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

preprint2013arXivOpen access

Abstract

A major open problem in the field of metric embedding is the existence of dimension reduction for nn-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\ell_p spaces with p>2p>2. In particular, we introduce an nn-point subset of ℓp\ell_p with doubling constant O(1), and demonstrate that any embedding of the set into ℓpd\ell_p^d with distortion DD must have D≥Ω((clog⁡nd)12−1p)D\geΩ\left(\left(\frac{c\log n}{d}\right)^{\frac{1}{2}-\frac{1}{p}}\right).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.