Approximate monotonicity of $\epsilon$-covering number

635 Views Asked by At

This is from Exercise 4.2.10 in Roman Vershynin's book, High-Dimensional Probability: An Introduction with Applications in Data Science.

Let $(T;d)$ be a metric space and $N(A,d,\epsilon)$ be the $\epsilon$-covering number of $A\subset T$ (the minimal cardinality of an $\epsilon$-net of $A$). Then for $A\subset B\subset T$, we have $$N(A,d,\epsilon)\le N(B,d,\epsilon/2), \forall\epsilon>0$$

How do we prove this inequality? In my opinion this is probably related to the exterior covering number, since Exterior Covering Number of $\epsilon /2$ is greater of equal than Covering Number of $\epsilon$, but I cannot get any further from here. Any help will be appreciated, thank you!

1

There are 1 best solutions below

1
On BEST ANSWER

Yes, we can use the exterior covering numbers :

\begin{equation} N(A,d, \epsilon) \le N^{ext}(A,d,\epsilon/2) \le N^{ext}(B,d,\epsilon/2) \le N(B,d,\epsilon/2) \end{equation}

The first and third inequalities are from exercise 4.2.9 and the second one follows from the inclusion and the definition of exterior covering numbers ( any exterior covering of B is also an exterior covering of A ).