Return to Question

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r\}.$

• With $\|\cdot \|$ the 2-norm, what is the distribution of

\begin{align} \underset{x \in S_r}{\min} \ \|X-x/\|x\|\| \end{align}

• How can this optimization be performed efficiently?

One idea for performing the optimization is by rounding onto the lattice along the ray $\alpha X$, varying $\alpha$ at each iteration to alter the fewest component's rounding possible. Then choosing the best value once $\alpha$ is small enough that $\alpha X$ rounds to zero. I believe this runs in no more than $O(n^2r).$

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r^2\}.$

• With $\|\cdot \|$ the 2-norm, what is the distribution (or at least the mean) of:

\begin{align} \underset{x \in S_r}{\min} \ \left\|X-\frac{x}{\|x\|}\right\|^2 \end{align}

• How can this optimization be performed efficiently?

One idea for performing the optimization is by exhaustion: the point in $S_r$ that attains the minimum will be a nearest-integer rounding of a point on the ray $\alpha X$. The values $\alpha$ for which $\operatorname{round}(\alpha X)$ changes can be readily computed. Then choose the best value once $\alpha$ is small enough that $\alpha X$ rounds to zero. However I am not sure what the complexity of this is in general.

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r\}.$

• With $\|\cdot \|$ the 2-norm, what is the distribution of

\begin{align} \underset{x \in S_r}{\min} \ \|X-x/\|x\|\| \end{align}

• How can this optimization be performed efficiently?
• What if instead of $S_r$ the optimization chooses points in $S_r+w$, with $w$'s components iid uniform on $[-1/2,1/2]$?

One idea for performing the optimization is by rounding onto the lattice along the ray $\alpha X$, varying $\alpha$ at each iteration to alter the fewest component's rounding possible. Then choosing the best value once $\alpha$ is small enough that $\alpha X$ rounds to zero. I believe this runs in no more than $O(n^2r).$

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r\}.$

• With $\|\cdot \|$ the 2-norm, what is the distribution of

\begin{align} \underset{x \in S_r}{\min} \ \|X-x/\|x\|\| \end{align}

• How can this optimization be performed efficiently?

One idea for performing the optimization is by rounding onto the lattice along the ray $\alpha X$, varying $\alpha$ at each iteration to alter the fewest component's rounding possible. Then choosing the best value once $\alpha$ is small enough that $\alpha X$ rounds to zero. I believe this runs in no more than $O(n^2r).$

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r\}.$ What is the distribution of

\begin{align} \underset{x \in S_r}{\min} \ \|X-x/\|x\|\| \end{align}

($\|\cdot \|$ is the 2-norm), or at least a bound on its mean?

What if instead of $S_r$ the optimization chooses points in $S_r+w$, with $w$'s components iid uniform on $[-1/2,1/2]$?

One simple idea for approximating the optimal point is to iterate: set $\alpha_k=\lfloor r \rfloor - k$, then choose the smallest $k$ where $\| \operatorname{round}(\alpha_k X) \|\leq r.$ This takes $O(rn)$.

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r\}.$

• With $\|\cdot \|$ the 2-norm, what is the distribution of

\begin{align} \underset{x \in S_r}{\min} \ \|X-x/\|x\|\| \end{align}

• How can this optimization be performed efficiently?
• What if instead of $S_r$ the optimization chooses points in $S_r+w$, with $w$'s components iid uniform on $[-1/2,1/2]$?

One idea for performing the optimization is by rounding onto the lattice along the ray $\alpha X$, varying $\alpha$ at each iteration to alter the fewest component's rounding possible. Then choosing the best value once $\alpha$ is small enough that $\alpha X$ rounds to zero. I believe this runs in no more than $O(n^2r).$