9
$\begingroup$

Let $B$ denote the unit ball on $\mathbb{R}^d$ and $N(\epsilon, B, d)$ be the cardinality of the smallest $\epsilon$-cover of $B$. An epsilon cover is a set $T \subset B$ such that for any $x \in B$, there is a $t \in T$ with $d(t,x) \le \epsilon$. See for example here. $N$ is referred to as the covering number, and $\log N$ is the Metric entropy.

Consider the following result: let $\|\cdot\|$ be a norm on $\mathbb{R}^d$ then $$ \frac{1}{\epsilon^d} \le N(\epsilon, B, \|\cdot\|) \le \left (1+\frac{2}{\epsilon} \right)^d. $$

I would like to know if there are bounds on the covering numbers that are dimension free when we choose the metric to be the Mahalanobis distance $d_S(x,y) = \|S^{-1/2}(x-y)\|_2$ for some positive definite covariance matrix $S$. Are there results along the lines of:

$$ \frac{1}{\epsilon^{f(S)}} \le N(\epsilon, B, d_S) \le \left (1+\frac{2}{\epsilon} \right)^{f(S)}. $$ where $f(S)$ is some quantity depending on $S$? An example I have in mind is when $S$ is diagonal with quickly decaying diagonal elements, e.g. $S_{ii} = i^{-2}$.

$\endgroup$

0

You must log in to answer this question.