0
$\begingroup$

Let $M$ be a metric space. Then the doubling dimension of $M$, denoted $\dim M$, is defined to be the minimum value $k$ such that every ball in $M$ of radius $r$ can be covered by at most $2^k$ balls of radius $r/2$.

In the paper "Small Hop-diameter Sparse Spanners for Doubling Metrics" by Chan/Gupta, the authors write:

Apart from being a generalization of the $\ell_p$ notion of dimension, designing algorithms that only use the doubling properties (instead of the geometry of $\mathbb R^k$) has other advantages: the notion of doubling dimension is fairly resistant to small perturbations in the distances: for instance, if one takes a distance matrix of a set of points in $\ell_p^k$ and slightly changes some of the entries, then the doubling dimension does not change by much, but the metric may not remain isometrically embeddable in $\ell_p$ (into any number of dimensions).

I have two related questions about this statement.

  1. Is there a known formalization of this stability, perhaps with respect to the Hausdorff distance on (finite) subsets of $\ell_p^k$? That is, do we have something like the following: Let $A$ and $B$ be finite subsets of $\ell_p^k$. Then $\lvert\dim A - \dim B\rvert \leq d_\text H(A,B)$, where $d_\text H$ is the Hausdorff distance?

  2. Does this stability generalize to arbitrary finite metric spaces, with respect to, e.g., the Gromov–Hausdorff distance? That is, if $A$ and $B$ are finite metric spaces, do we have something like $\lvert\dim A - \dim B\rvert \leq d_\text{GH}(A,B)$, where $d_\text{GH}$ is the Gromov–Hausdorff distance?

If 'No' to the above, are there any sensible formalizations of Chan & Gupta's statement that make their claim of stability precise?

$\endgroup$

1 Answer 1

0
$\begingroup$

I have come to the conclusion that my questions $1$ and $2$ can be seen to be false by considering simple examples in $\mathbb R$. Morally, since doubling dimension takes only integer values, a general stability result is not possible in the sense that I describe.

However, after further reading, I believe what Chan & Gupta are referring to is the robustness result given as Propsition $3$ in "Bypassing the Embedding" by Talwar:

Proposition 3 [Robustness]. Let $(X, d)$ and $(Y, d')$ be metric spaces such that there is a bijective map $f: X \rightarrow Y$ satisfying $d\left(x_1, x_2\right) \leq$ $d' \left(f\left(x_1\right), f\left(x_2\right)\right) \leq D \cdot d\left(x_1, x_2\right)$. Then $k_Y \leq 2 k_X \cdot\lceil\log 4 D\rceil$.

Note that Talwar denotes the doubling dimension of $X$ by $k_{X}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.