4
$\begingroup$

Consider linear subspaces of $\mathbb{R}^n$. For two subspaces $X$ and $Y$, we define their Hausdorff distance as $$ {\displaystyle d_{\mathrm {H} }(X,Y)=\max \left\{\,\sup _{x\in X, |x|_2=1}\inf _{y\in Y,|y|_2=1}d(x,y),\,\sup _{y\in Y,|y|_2=1}\inf _{x\in X, |x|_2=1}d(x,y)\,\right\}.\!} $$

For $\epsilon>0$, the set of subspaces $X_1,\dots,X_m$ is called an $\epsilon$-net under Hausdorff distance if for any subspace $Y$, there is some $X_i$ such that $$ d_{\mathrm {H} }(X_i,Y)<\epsilon. $$ The questions is to provide upper and lower bound of $m$.

It is direct to observe that if $X$ and $Y$ have different dimensions, their distance is always greater than 1.

Therefore, we only need to consider $m=\sum_{k=1}^n m_k$, where $m_k$ denotes the $\epsilon$-net of fixed ($k$) dimensional subspaces.

Also, it would be interesting to consider another definition of Hausdorff distance as $$ {\displaystyle d_{\mathrm {H} }(X,Y)=\max \left\{\,\sup _{x\in X, |x|_2\leq 1}\inf _{y\in Y,|y|_2\leq 1}d(x,y),\,\sup _{y\in Y,|y|_2\leq1}\inf _{x\in X, |x|_2\leq 1}d(x,y)\,\right\}.\!} $$

Would the difference between the distance induces a significant difference between the bound of the $\epsilon$-net?

$\endgroup$
4
  • $\begingroup$ I guess you assume that $X$ and $Y$ are bounded (and maybe closed and nonempty). Still the space of such sets is not compact, so it has no nets. If you restrict to subsets in a bounded set $B$, with an $\varepsilon$-net $N$, then the set of all nonempty subsets in $N$ is an $\varepsilon$-net in the space of subsets in $B$. So, if $n=|N|$, then $m=2^n-1$. $\endgroup$ Commented Feb 24, 2020 at 4:15
  • $\begingroup$ Perhaps it'd be simpler to restrict the linear subspaces to dimension $\ >0\ $ and $\ <n.$ Furthermore, one could concentrate on the subspaces of a fixed dimension $\ k,\ $ thus looking at $\ m_1\ldots m_{n-1}.\ $ Then, it'd be rather straightforward to pass to the overall $\ m.$ $\endgroup$
    – Wlod AA
    Commented Feb 24, 2020 at 5:36
  • $\begingroup$ @AntonPetrunin, everything seems to be fine (but for taking certain terminology liberty). Of course, we could more properly talk about the Hausdorff distances between the respective unit spheres. $\endgroup$
    – Wlod AA
    Commented Feb 24, 2020 at 5:40
  • $\begingroup$ By "upper bound of $m$", I think you mean "upper bound on the least $m$ for which such an $\epsilon$-net exists". Otherwise, given any $\epsilon$-net, you can always enlarge it as much as you wish by throwing in more subspaces. $\endgroup$ Commented Feb 24, 2020 at 17:51

0

You must log in to answer this question.

Browse other questions tagged .