2
$\begingroup$

I am trying to solve the following approximation problem on the general unit sphere $S^{n-1} \subseteq \mathbb{R}^n$. First, let $\theta \in (0, \pi)$ be a fixed angle, and $r \in S^{n-1}$ a fixed unit vector. Then you can define a subset $R \subseteq S^{n-1}$ containing all the vectors that are at most an angle of $\theta$ away from $r$.

\begin{equation} R = \{x \in S^{n-1} : \langle x, r \rangle \ge \cos(\theta)\} \end{equation}

The approximation problem I am trying to solve is now as follows.

Given an arbitrary $v \in S^{n-1}$, find a vector $w \in R$ that is closest to $v$. In other words, solve the following minimization problem:

\begin{equation} w = \text{argmin } \|v - x\|_2 \quad\text{for all } x \in R \end{equation}

I have tried finding the solution intuitively, by considering what happens in $\mathbb{R}^3$, and basically hoping my solution there generalizes to $\mathbb{R}^n$. The proposed solution I came up with is as follows.

First, if $v \in R$, then the solution is trivially given by $w = v$. So now assume $v \notin R$, which means $\langle v, r \rangle < \cos(\theta)$. Then define $x = v - \langle v, r \rangle r$, consequently the solution is given by \begin{equation} w = \frac{\sin(\theta)}{\|x\|} \cdot x + \cos(\theta) \cdot r \ \end{equation}

The idea is, if $v \notin R$, you assume the solution $w$ will be both in the plane spanned by $v$ and $r$, and also on the "border" of the set $R$, in other words $\langle w, r \rangle = \cos(\theta)$. So you consider the affine hyperplane which passes through the point $\cos(\theta) \cdot r$ and is perpendicular to the vector $r$. This is basically the hyperplane that "slices" your unit sphere between $R$ and $R^c$ and thus contains the aforementioned border. If you intersect this hyperplane with the plane spanned by $v$ and $r$, eventually you should get the solution I came up with, assuming my calculations were correct.

Now I have been able to prove that my solution is both contained in $S^{n-1}$, and $R$, simply by working out the inproducts $\langle w, w \rangle = 1$ and $\langle w, r \rangle = \cos(\theta)$. However I cannot seem to prove the original statement, that this $w$ indeed minimizes the norm $\|v - x\|_2$. To cut down potential work done by people trying to help, I'm going to put some of these results down here as well. Below I will define $\langle v, r \rangle = \cos(\phi) < \cos(\theta)$, and also introduce a vector $u \in R$ such that $\|u - v\| \le \|w - v\|$ or equivalently, $\langle u, v \rangle \ge \langle w, v \rangle$. If all my work is correct, the following statements should be true.

\begin{align*} \langle v, w \rangle &= \sin(\theta)\sin(\phi) + \cos(\theta)\cos(\phi) \\ \langle u, w \rangle &= \frac{\sin(\theta)}{\sin(\phi)}\langle u, v \rangle - \frac{\sin(\theta)}{\tan(\phi)} \langle u, r \rangle + \cos(\theta)\cos(\phi) \\ &\ge 1 + \cos(\theta)(\cos(\phi) - \cos(\theta)) \end{align*}

Can anyone help me figure out how to prove my solution indeed works? Or alternatively, point out why it doesn't?

Footnote: In writing this I became aware of the pathological case where $v = -r$, which would mean the solution set contains the entire border of $R$ (right?). This leaves me wondering if this is the only case when multiple solutions exist or not. If it seems that multiple solutions can be found in non-pathological cases, it would be of great help if I were able to explicitly define the entire solution set, if at all possible.

$\endgroup$
0
$\begingroup$

Okay, I think I might have figured it out. I would kindly request someone to look over my work to make sure I haven't made any mistakes. The trick was to work towards $u$'s unit length in the system of inequalities. Here goes...

Assume $u \in R$ is a better solution than $w$, i.e. $\langle u, v \rangle \ge \langle w, v \rangle$. Since inproducts are invariant under orthogonal transformations, we can perform such a transformation to allow $r = e_1$, and $v = (\cos(\phi), \sin(\phi), 0, \dots, 0)$ for some $\phi \in (0, \pi)$ to be in the xy-plane (the latter of which is trivially true in the case $n = 2$). From the definition of $w$ it immediately follows that $w = (\cos(\theta), \sin(\theta), 0 \dots 0)$. Since $u \in R$, it follows that $u_1 = \langle u, r \rangle \ge \cos(\theta)$. Secondly we know that

\begin{equation} \langle v, u \rangle = \cos(\phi) u_1 + \sin(\phi) u_2 \end{equation}

on one hand, per definition of the inproduct. On the other hand, we also know that

\begin{equation} \langle v, u \rangle \ge \langle v, w \rangle = \sin(\theta)\sin(\phi) + \cos(\theta)\cos(\phi) \end{equation}

per the assumption on $u$. Since $\phi \in [0, \pi)$, this means $\sin(\phi) \ge 0$. Putting the two previous (in)equalities together we can deduce that

\begin{equation} u_2 \ge \sin(\theta) + \frac{\cos(\theta) - u_1}{\tan(\phi)} \end{equation}

However since we already know that $u_1 \ge \cos(\theta)$, it immediately follows that $u_2 \ge \sin(\theta)$. Since $u$ is supposed to be a unit vector, it can only possibly be $u = (\cos(\theta), \sin(\theta), 0 \dots 0) = w$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.