17

I am interested in probabilistic or explicit ways to construct an $\epsilon$-net of the $l_2$ unit ball in $\mathbb{R}^{d}$.

I know that, for every $\epsilon > 0$, there exists an $\epsilon$-net $\mathcal{N}_{\epsilon}$ for the unit sphere in $d$ dimensions such that $$ M\triangleq\left|\mathcal{N}_{\epsilon}\right| \le \left( 1+\frac{2}{\epsilon}\right)^{d}. $$ (Lemma 5.2 in https://arxiv.org/abs/1011.3027) To my understanding, the aforementioned bound holds for an $\epsilon$-net of the entire ball, not only the sphere.

In the case of the sphere, we can construct an $\epsilon$-net with high probability, by drawing a sufficient number ($O(M\log{M})$) of independent random vectors according to a Gaussian distribution $N(\mathbf{0}, \mathbf{I})$, and normalizing the length to $1$. I believe that one way to get an $\epsilon$-net for the ball, would be to repeat the above procedure $O(1/\epsilon)$ times, for all spheres of radii $\epsilon, 2\epsilon,3\epsilon, \dots, 1$. The union of the $\epsilon$-nets, should be able to cover the ball. However, it would require $\tilde{O}\left((1+2/{\epsilon})^{d+1}\right)$ points (ignoring the logarithmic factor).

  • Is there a simple way to construct an $\epsilon$-net for the unit ball directly, $\textit{i.e.}$, without constructing nets for multiple spheres?
  • Is there way to achieve the bound on $\left|\mathcal{N}_{\epsilon}\right|$ (possibly up to logarithmic factors)?

I would appreciate any pointers to either probabilistic or explicit methods.

Clement C.
  • 67,323
megas
  • 2,276

2 Answers2

3

We can use surface area instead of volume.

Let $N_\epsilon$ be a subset of $S^{n-1}$ (embedded in $\mathbb{R}^n$) such that any two points in $N_\epsilon$ have distance strictly greater than $\epsilon$ and $N_\epsilon$ is maixmal. This means that the balls of radius $\epsilon/2$ centered at points in $N_\epsilon$ are disjoint and are contained in $B(0,1+\epsilon/2)$ and are outside the ball $B(0,1-\epsilon/2)$. Let $V(r)$ be the volume of the $n$ dimensional ball of radius $r$ and let $S(r)$ be the surafce area of the ball of radius $r$. Then \begin{align*} |N_\epsilon| V(\epsilon/2) &\le V(1+\epsilon/2) - V(1-\epsilon/2) \\ &= \int_{1-\epsilon/2}^{1+\epsilon/2} S(r) dr \\ &\le \int_{1-\epsilon/2}^{1+\epsilon/2} S(1+\epsilon/2) dr \\ &= \epsilon S(1+\epsilon/2) \\ &= \epsilon (1+\epsilon/2)^{n-1} S(1) \end{align*}

Then using the relation between the volume and the surface area, we get that $$ |N_\epsilon| \le \epsilon (1+\epsilon/2)^{n-1} \frac{2^n}{\epsilon^n} \frac{S(1)}{V(1)} = 2n \left(1+\frac{2}{\epsilon}\right)^{n-1}. $$

Here we gained a factor of $n$ in front, but we reduced the power from $n$ to $n-1$. Hence when $\epsilon$ is small, this is a better bound than the volumetric bound.

Rishi Sonthalia
  • 1,906
0

One can take a random lattice $\Lambda\subset\mathbb R^n$, e.g., a random Construction-A lattice. It is known that such lattices are good for covering (with high pribability), i.e., $r_{\text{cov}}(\Lambda) = r_{\text{eff}}(\Lambda)(1+o(1))$. See Theorem 2 here. (It is pretty nontrivial to prove.) By covering goodness, if one takes $r_{\text{cov}}(\Lambda) = \epsilon$, then 1) $\Lambda\cap B_2^n$ (where $B_2^n$ is the unit $\ell_2$ ball) is an $\epsilon$-net of $B_2^n$; 2) $|\Lambda\cap B_2^n|\le\frac{\text{vol}(B_2^n+\epsilon B_2^n)}{r_{\text{cov}}(\Lambda)B_2^n}=(1+1/\epsilon)^n$.

Haar lattices should also do the job, though I don't have a reference in mind. Maybe check out papers by C. A. Rogers.

If you don't like lattices (they're linear and it's hard to prove covering properties), then I'm reasonably confident that a (homogeneous) Poisson point process (with appropriate intensity) restricted to a ball should satisfy your requirements with high probability. Not sure if this is proved anywhere but it should be much easier to prove than lattices.

As far as I understand, constructing explicit $\epsilon$-nets meeting existential bounds is a hard question. Theoretical computer scientists may care about it. See e.g. this, though I did not read it myself.

Yihan Zhang
  • 163