# Vector Approximation on The Unit Sphere

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$$.

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

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:

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

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 $$$$w = \frac{\sin(\theta)}{\|x\|} \cdot x + \cos(\theta) \cdot r \$$$$

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.

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

$$$$\langle v, u \rangle = \cos(\phi) u_1 + \sin(\phi) u_2$$$$

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

$$$$\langle v, u \rangle \ge \langle v, w \rangle = \sin(\theta)\sin(\phi) + \cos(\theta)\cos(\phi)$$$$

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

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

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$$.