A question about the property of covering numbers

122 Views Asked by At

I am reading the book "Multivariate approximation"(Page 321 - 322) written by V. Temlyakov and thinking about the following property of covering numbers:

Let $X$ be a Banach space and let $B_X$ denote the unit ball of $X$ whose center is at $0$.

Denote $N_{\epsilon}(A,X):=\min\{n: \exists y^1, y^2, ... ,y^n: A\subset \cup_{j=1}^n B_X(y^j,\epsilon)\}$.

Prove that: $$N_{\epsilon_1\epsilon_2}(A,X)\leq N_{\epsilon_1}(A, X)\cdot N_{\epsilon_2}(B_X, X).$$

The author says this is obvious but I am a bit of confusion.

My idea here is to use other balls in $X$ to cover the balls $B_X(y^j,\epsilon)$ again but I have no idea why the right-hand side is the product of two covering numbers.

Any suggestions would be welcome and thank you !!

1

There are 1 best solutions below

2
On BEST ANSWER

Your idea is on the right track. We start off by covering $A$ with $N_{\epsilon_1}(A,X)$ balls of radius $\epsilon_1$, and then cover each of those balls by $N_{\epsilon_2}(B_X,X)$ balls of radius $\epsilon_1\epsilon_2$. This produces a cover of $A$ by $N_{\epsilon_1}(A,X)\cdot N_{\epsilon_2}(B_X,X)$ balls of radius $\epsilon_1\epsilon_2$ and proves the covering number inequality.

Now, to prove we can cover a radius $\epsilon_1$ ball by $N(B_X,X)$ balls of radius $\epsilon_1\epsilon_2$:

Since $B(y,\epsilon_1)= y+B(0,\epsilon_1)$, we can WLOG work with a ball at the origin. Note that $\delta B_X = B_X(0,\delta)$ for $\delta>0$ by homogeneity, where by $\delta A$ I mean the set of scalings $\{\delta a:a\in A\}$. If $m:=N_{\epsilon_2}(B_X,X)$, then there are $m$ balls centered at points $y^1,\dotsc, y^m$ such that $$B_X\subset B(y^1,\epsilon_2)\cup\dotsm \cup B(y^m,\epsilon_2),$$ so $$B(0,\epsilon_1) = \epsilon_1 B_X \subset \epsilon_1B(y^1,\epsilon_2)\cup\dotsm\cup\epsilon_1 B(y^m,\epsilon_2)$$ where I use the fact that $\delta(A\cup B)\subset \delta A\cup \delta B$ for $A,B$ subsets of a Banach space. We also have $\epsilon_1B(y,\epsilon_2) = B(\epsilon_1y,\epsilon_1\epsilon_2)$, which is an easy exercise in definitions. Hence we have covered $B(0,\epsilon_1)$ by $m$ balls of radius $\epsilon_1\epsilon_2$, as desired.