Relationship between covering number of metric spaces related through operator norm.

222 Views Asked by At

Given two normed vector spaces $V$ and $W$, a linear map $A : V \rightarrow W$ and a costant $c$ such that

\begin{equation*} \|Av\|\leq c\|v\|, \qquad \forall v\in V \end{equation*}

Note that the norm on the left is the one in $W$ and the norm on the right is the one in $V$. Intuitively, the operator $A$ never increases the length of any vector more than by a factor of $c$.

Can anything be said about the covering number of $W$ in terms of the covering number of $V$?

1

There are 1 best solutions below

0
On

A trivial case where no information can be obtained is when $A$ is the $0$ operator, in which case it satisfies the desired bound, but gives no information about $W$ at all.

Even when we exclude singular operators, however, we might still run into problems. Consider a sequence of linear operators $A_{n}:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2},$ where both domain and target have the usual norm $\|\cdot\|_{2},$ defined by $A_{n}e_{1}=e_{1},$ $A_{n}e_{2}=\frac{1}{n}e_{2},$ where $e_{1},e_{2}$ are the ordinary standard unit vectors. In this example, we clearly have equality in the covering numbers between $V$ and $W$ (they are the same space), and for all $n,$ $\|A_{n}x\|_{2}\leq \|x\|_{2}$ for all $x\in\mathbb{R}^{2}.$ However, if we try to obtain a covering for the unit ball in $\mathbb{R}^{2}$ using a covering for the preimage of the unit ball under $A_{n},$ which is the ellipse with minor axis $\{(x,0):-1\leq x\leq 1\}$ and major axis $\{(0,y):-n\leq y\leq n\},$ we see that the number of balls of fixed size required to cover this preimage can be made arbitrarily large by increasing $n.$ That is, if all we knew about $W$ was the information we could glean from the linear operator $A,$ it might appear that we need many more balls of fixed size to cover a set than we do in reality.

If $A$ is invertible, and you have a bound on the condition number of $A$, using the induced norms on $\mathcal{L}(V,W)$ and $\mathcal{L}(W,V),$ that is, for the norms $$\|B\|_{V\rightarrow W}:=\mathrm{sup}_{\|x\|_{V}\leq 1}\|Bx\|_{W},\quad \|C\|_{W\rightarrow V}:=\mathrm{sup}_{\|x\|_{W}\leq 1}\|Cx\|_{V},$$ defined for $B:V\rightarrow W$, $C:W\rightarrow V,$ you have a bound on the quantity $\kappa(A):=\|A\|_{V\rightarrow W}\|A^{-1}\|_{W\rightarrow V},$ then it might be possible to obtain the kind of result you're looking for. Note that when $\|Ax\|_{W}\leq C\|x\|_{V}$ for all $x\in V,$ this means that $\|A\|_{V\rightarrow W}\leq C,$ so these norms can be interpreted as the "best possible constant" $C$ that may appear in that inequality. But because of the example above, I think that you need to have control over this constant for both the linear operator $A$ as well as its inverse (observe that $\kappa(A_{n})=n$ for all $n\geq 1$ in that example).