Fdtxjr

Won the lottery - how do I keep the money?

Complex fractions

Has this building technique been used in an official set?

Anatomically Correct Strange Women In Ponds Distributing Swords

Novel about a guy who is possessed by the divine essence and the world ends?

Is it professional to write unrelated content in an almost-empty email?

Multiple labels for a single equation

How does the mv command work with external drives?

Would a galaxy be visible from outside, but nearby?

Why do we use the plural of movies in this phrase "We went to the movies last night."?

Why is the US ranked as #45 in Press Freedom ratings, despite its extremely permissive free speech laws?

Is there a difference between "Fahrstuhl" and "Aufzug"

If a black hole is created from light, can this black hole then move at speed of light?

How to Reset Passwords on Multiple Websites Easily?

What does "Its cash flow is deeply negative" mean?

Does it take more energy to get to Venus or to Mars?

Is "for causing autism in X" grammatical?

Help understanding this unsettling image of Titan, Epimetheus, and Saturn's rings?

WOW air has ceased operation, can I get my tickets refunded?

Can you replace a racial trait cantrip when leveling up?

How to count occurrences of text in a file?

How do I go from 300 unfinished/half written blog posts, to published posts?

What happened in Rome, when the western empire "fell"?

How to avoid supervisors with prejudiced views?

Constructing an $epsilon$-net of $l_2$ unit ball

7

2

$begingroup$

I am interested in probabilistic or explicit ways to construct an $epsilon$-net of the $l_2$ unit ball in $mathbbR^d$.

I know that, for every $epsilon > 0$, there exists an $epsilon$-net $mathcalN_epsilon$ for the unit sphere in $d$ dimensions such that
$$
Mtriangleqleft|mathcalN_epsilonright|
le left( 1+frac2epsilonright)^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(MlogM)$) of independent random vectors according to a Gaussian distribution $N(mathbf0, mathbfI)$, 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, 2epsilon,3epsilon, dots, 1$.
The union of the $epsilon$-nets, should be able to cover the ball.
However, it would require $tildeOleft((1+2/epsilon)^d+1right)$ points (ignoring the logarithmic factor).

• Is there a simple way to construct an $epsilon$-net for the unit ball directly, $textiti.e.$, without constructing nets for multiple spheres?


• Is there way to achieve the bound on $left|mathcalN_epsilonright|$ (possibly up to logarithmic factors)?

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

probability

share|cite|improve this question

edited Mar 18 at 20:35

Clement C.

51k34093

asked Nov 9 '14 at 20:57

megasmegas

1,801614

$endgroup$

add a comment | 

7

2

$begingroup$

I am interested in probabilistic or explicit ways to construct an $epsilon$-net of the $l_2$ unit ball in $mathbbR^d$.

I know that, for every $epsilon > 0$, there exists an $epsilon$-net $mathcalN_epsilon$ for the unit sphere in $d$ dimensions such that
$$
Mtriangleqleft|mathcalN_epsilonright|
le left( 1+frac2epsilonright)^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(MlogM)$) of independent random vectors according to a Gaussian distribution $N(mathbf0, mathbfI)$, 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, 2epsilon,3epsilon, dots, 1$.
The union of the $epsilon$-nets, should be able to cover the ball.
However, it would require $tildeOleft((1+2/epsilon)^d+1right)$ points (ignoring the logarithmic factor).

• Is there a simple way to construct an $epsilon$-net for the unit ball directly, $textiti.e.$, without constructing nets for multiple spheres?


• Is there way to achieve the bound on $left|mathcalN_epsilonright|$ (possibly up to logarithmic factors)?

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

probability

share|cite|improve this question

edited Mar 18 at 20:35

Clement C.

51k34093

asked Nov 9 '14 at 20:57

megasmegas

1,801614

$endgroup$

add a comment | 

$begingroup$

I am interested in probabilistic or explicit ways to construct an $epsilon$-net of the $l_2$ unit ball in $mathbbR^d$.

I know that, for every $epsilon > 0$, there exists an $epsilon$-net $mathcalN_epsilon$ for the unit sphere in $d$ dimensions such that
$$
Mtriangleqleft|mathcalN_epsilonright|
le left( 1+frac2epsilonright)^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(MlogM)$) of independent random vectors according to a Gaussian distribution $N(mathbf0, mathbfI)$, 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, 2epsilon,3epsilon, dots, 1$.
The union of the $epsilon$-nets, should be able to cover the ball.
However, it would require $tildeOleft((1+2/epsilon)^d+1right)$ points (ignoring the logarithmic factor).

• Is there a simple way to construct an $epsilon$-net for the unit ball directly, $textiti.e.$, without constructing nets for multiple spheres?


• Is there way to achieve the bound on $left|mathcalN_epsilonright|$ (possibly up to logarithmic factors)?

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

probability

share|cite|improve this question

edited Mar 18 at 20:35

Clement C.

51k34093

asked Nov 9 '14 at 20:57

megasmegas

1,801614

$endgroup$

share|cite|improve this question

edited Mar 18 at 20:35

Clement C.

51k34093

asked Nov 9 '14 at 20:57

megasmegas

1,801614

share|cite|improve this question

edited Mar 18 at 20:35

Clement C.

51k34093

asked Nov 9 '14 at 20:57

megasmegas

1,801614

edited Mar 18 at 20:35

Clement C.

51k34093

edited Mar 18 at 20:35

Clement C.

51k34093

asked Nov 9 '14 at 20:57

megasmegas

1,801614

asked Nov 9 '14 at 20:57

megasmegas

1,801614