What is the covering number $N(\epsilon, B_2, ||\cdot||_2)$ of a ball $B_2$ in $\mathbb{R}^d$ of radius $r$ under the $l_2$ norm?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ In what space exactly? $\endgroup$– Nate EldredgeCommented Apr 1, 2020 at 21:34
-
$\begingroup$ @NateEldredge The space is $\mathbb{R}^d$ for some dimension $d$. And the ball is the $l_2$ ball. $\endgroup$– kkcCommented Apr 1, 2020 at 21:43
-
$\begingroup$ Okay. The focus on $l^2$ and the banach-spaces tag made it sound like you had infinite-dimensional spaces in mind. $\endgroup$– Nate EldredgeCommented Apr 1, 2020 at 22:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The $\epsilon$-covering number of the euclidean unit ball in $\mathbb R^d$ scales like $(1/\epsilon)^d$. More formally,
Lemma. If $\epsilon < 1$, then $(1/\epsilon)^d \le N(\epsilon, B_2) \le (3/\epsilon)^d$. Else $N(\epsilon,B_2) = 1$.
Proof. See Theorem 4.2 and Example 14.1 of this manuscript http://www.stat.yale.edu/~yw562/teaching/598/lec14.pdf. $\quad\quad\Box$
Now, use this to get (an estimate of) the covering number of $rB_2$, for any $r \ge 0$.
