Dtjytyk

ssTTsSTtRrriinInnnnNNNIiinngg

CAST throwing error when run in stored procedure but not when run as raw query

GFCI outlets - can they be repaired? Are they really needed at the end of a circuit?

Short story with a alien planet, government officials must wear exploding medallions

Intersection Puzzle

Is it inappropriate for a student to attend their mentor's dissertation defense?

Assassin's bullet with mercury

Im going to France and my passport expires June 19th

Why doesn't using multiple commands with a || or && conditional work?

How to prevent "they're falling in love" trope

Should I cover my bicycle overnight while bikepacking?

Should I tell management that I intend to leave due to bad software development practices?

What reasons are there for a Capitalist to oppose a 100% inheritance tax?

Why would the Red Woman birth a shadow if she worshipped the Lord of the Light?

Why no variance term in Bayesian logistic regression?

What exploit are these user agents trying to use?

How to show a landlord what we have in savings?

How did the Super Star Destroyer Executor get destroyed exactly?

Venezuelan girlfriend wants to travel the USA to be with me. What is the process?

Why didn't Boeing produce its own regional jet?

What killed these X2 caps?

Is there an expression that means doing something right before you will need it rather than doing it in case you might need it?

Is it possible to create a QR code using text?

What mechanic is there to disable a threat instead of killing it?

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

can I bound the following probability?Bounding the estimation error of flipped bit-vector sum using Chernoff boundBayesian posterior with truncated normal priorinequality for real-valued Gaussian sumsAverage distance between two points on a unit square.How to calculate the probability of this summation?Distribution of the output of additive white Gaussian channelFeasible region of probabilistic constraintThe point probability of a random variableBounding coefficients of a uniform unit vector projected in a basis

7

2

$begingroup$

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
$$
Mtriangleqleft|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(Mlog{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, 2epsilon,3epsilon, 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.

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 $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
$$
Mtriangleqleft|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(Mlog{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, 2epsilon,3epsilon, 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.

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 $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
$$
Mtriangleqleft|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(Mlog{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, 2epsilon,3epsilon, 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.

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