The direction that gets me closest to a given point in $\mathbb{R}^n$

Question

Let $p \in \mathbb{R}^{n}$ and $p=\lambda_1 e_1+...+\lambda_n e_n$ where $e_i$ are standard basis vectors then if I want to find the component along which I can get closest to the point $p$ then it will just be $e_j$ with $j \in \{1,...,n\}$ such that $\lambda_j$ satisfies $|\lambda_j| = max_{1 \leq i\ \leq n} \{|\lambda_1|,...,|\lambda_n|\}$ and the closest point to $p$ along this direction is $ \lambda_j e_j$. As $\lambda_j$ was maximum, we have \begin{equation*}|\lambda_j| \geq \frac{|p|}{\sqrt{n}} \end{equation*} and \begin{equation} |\lambda_j e_j - p | \leq \sqrt{\frac {n-1} {n} } |p|. \end{equation}

I am looking for similar estimates when $p$ is represented by a different basis. What can I say if the point $p= \alpha_1 x_1 +...+\alpha_n x_n$ where $\{x_1,...,x_n\}$ are such that $ \angle(x_i, \text{span}(x_1,...,x_{i-1})) \geq \theta$ for $i=2,...,n$ and $\theta >0$. Can I choose a direction $x_j$, $j \in \{1,...,n\}$ so that $|\alpha x_j - p| \leq C |p|$ where $\alpha>0$, $C<1$ and may depend on $n$ and $\theta$?

This is a repost from stackexchange (https://math.stackexchange.com/questions/4041205/the-direction-that-gets-me-closest-to-a-given-point-in-mathbbrn) where I got no answers. Hopefully it's OK to repeat the question here.

Answer 1

For $p, x_i\in \mathbb{R}^n$, with $1\le i\le n$, define $$\theta_i=\angle(x_i,\text{span}(\{x_j \;|\; j\ne i\})),\quad \theta=\min(\{\theta_i\})$$

$$\beta_i=\frac{\pi}{2}-\angle(p,x_i),\quad\beta=\max(\{\beta_i\})$$

CLAIM. $$\sin(\beta)\ge\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}$$

PROOF. Trivial if $\theta=0$, so assume $\theta>0$. Write $p$ and the $x_i$'s as $1\times n$ matrices and rescale them so that $pp^T=x_i x_i^T=1$. Let $X$ be the matrix with rows $x_1,\dots x_n$. Then $\theta>0$ implies that $X$ is invertible, therefore

$$(pX^T)(XX^T)^{-1}(pX^T)^T=pp^T=1$$

But $pX^T=(\sin(\beta_1),\dots \sin(\beta_n))$ and the inverse correlation matrix $(XX^T)^{-1}=(c_{ij})$ satisfies

$$\displaystyle c_{ij}=\frac{1}{\sin(\theta_i)\sin(\theta_j)}\cdot \frac{x'_i {x'_j}^T}{|x'_i||x'_j|}$$

where $x'_i$ is the component of $x_i$ orthogonal to $\text{span}(\{x_j \;|\; j\ne i\})$. (Different proofs can be found here and here, but a standard linear algebra text reference would be welcome.) Moreover $x'_j \perp x_i$ for $j\ne i$ also implies $\text{span}(\{x'_j \;|\; j\ne i\}$ is the hyperplane orthogonal to $x_i$, and thus $\angle(x'_i,\text{span}(\{x'_j\;|\; j\ne i\}))=\angle(\text{span}(\{x_j \;|\; j\ne i\}),x_i)=\theta_i$ and then $\angle(x'_i,x'_j)\ge \max(\theta_i,\theta_j)\ge \theta$. In conclusion

$$\displaystyle |c_{ij}|\le \frac{\cos(\theta)}{\sin(\theta)^2}\quad\text{if } i\ne j$$ $$\displaystyle |c_{ii}|\le \frac{1}{\sin(\theta)^2}$$

and therefore $$1=\sum_{i,j}c_{ij}\sin(\beta_i)\sin(\beta_j)\le \sin(\beta)^2\sum_{i,j}|c_{ij}|\le \sin(\beta)^2\frac{n+(n^2-n)\cos(\theta)}{\sin(\theta)^2}$$ $$\sin(\beta)\ge\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}$$

This also implies the good (as $\theta\rightarrow 0$) first order approximation $\sin(\beta)\ge \sin(\theta)/n$. $\quad\blacksquare$

I verified empirically that $\frac{sin(\theta)}{\sqrt{n(1+(n-1)\cos(\theta))}}\ge \sin(\frac{\theta}{n})$, which would imply $\beta\ge\frac{\theta}{n}$ too, but I'll leave the proof of that as an exercise, if true.

The example in my other answer led me to conjecture that the best possible result should be $$\sin(\beta)\ge \sin(\theta)\sqrt{\frac{(n-1)\tan(\theta)^2+n}{n((n-1)\tan(\theta)^2+n^2)}}$$

which is not much stonger than the claim, but probably much harder to prove.

Answer 2

This is a pair of long comments, not an answer. Hopefully it can help towards a full answer.

• First, I intend to show that the separation condition on the $x_i$ vectors formulated in the question may not be the right one.
• Second, I will produce what I think may be be the worst scenario under a stronger separation assumption, and consequently conjecture the specific formula that one may want to try to prove.

---

The question assumes $\forall i:\angle(x_i,\text{span}(x_1,...,x_{i-1})) \ge \theta$. This does not imply that $\forall i:\angle(x_i,\text{span}(\{x_j\;|\;j\ne i\})) \ge \theta$. To see that, for a small $\theta>0$ consider the $\mathbb{R}^3$ vectors

$x_1=(\sin(\theta),\cos(\theta),0)$

$x_2=(0,1,0)$

$x_3=(-\cos(\theta),0,\sin(\theta))$

Then it's easy to check that

• $\angle(x_1,x_2)=\theta$
• $\text{span}(x_1,x_2)=xy$-plane
• $\angle(x_3,\text{span}(x_1,x_2))=\theta$
• $\text{span}(x_2,x_3)=xy$-plane tilted by $\theta$ around the $y$-axis
• $x'_1:=$ component of $x_1$ orthogonal to $\text{span}(x_2,x_3)$ $=x_1-\cos(\theta)x_2+\cos(\theta)\sin(\theta)x_3= (\sin(\theta)-\sin(\theta)\cos(\theta)^2,0,\sin(\theta)^2\cos(\theta))$
• since $|x_1|=1$, $\sin(\angle(x_1,\text{span}(x_2,x_3)))^2=x'_1\cdot x_1=\sin(\theta)^4$
• hence $\angle(x_1,\text{span}(x_2,x_3))=O(\theta^2)$ as $\theta$ approaches $0$.
• finally, taking $p$ to be a vector orthogonal to the $(x_2,x_3)$-plane, the closest $x_i$ to $p$ is $x_1$ and the angle of separation is then $\pi/2-O(\theta^2)$.

I suspect the OP had in mind a stronger result (in $\theta$), which is not possible with the weak separation condition assumed.

---

The following example in $\mathbb{R}^n$ assumes the strong separation condition; in that case I conjecture that it is the worst possible scenario, which would imply that the smallest $\angle(x_i, p)$ is $\le \pi/2-\theta/n$.

Fix $0 \le h \le 1$ and define

$p=(1,1,\dots 1)$

$x_i=ne_i-p+h p$

Notice that $\text{span} (\{x_i\})$ is the hyperplane orthogonal to $p$ for $h=0$, and that for $h=1$ the $x_i$'s are maximally separated, that is orthogonal. So assume $0 < h\le 1$.

If $\alpha$ is the angle between $p$ and any of the $x_i$'s, then

$$\sin(\frac{\pi}{2}-\alpha)=\cos(\alpha)=\frac{x_i\cdot p}{\sqrt{(p\cdot p)(x_i\cdot x_i)}}=\frac{h n}{\sqrt{n\big(n^2+n(1-h)^2-2n(1-h)\big)}}=\frac{h}{\sqrt{n-1+h^2}}$$

The angle $\theta$ between $x_i$ and $\text{span}(\{x_j \;\vert\; j\ne i\})$ is, for symmetry reasons, the same as the angle between $x_i$ and $\displaystyle \sum_{j\ne i} -x_j=x_i-nh p$: $$\cos(\theta)=\frac{-n^2h^2+n(n-1+h^2)}{\sqrt{n(n-1+h^2)\big(n^3h^2-2n^2h^2+n(n-1+h^2)\big)}}=\frac{(1-h^2)\sqrt{n-1}}{\sqrt{(n-1+h^2)(h^2 n-h^2+1)}}$$

and therefore

$$\sin(\theta)=\frac{h n}{\sqrt{(n-1+h^2)(h^2 n-h^2+1)}}$$

In conclusion

$$\frac{\sin(\frac{\pi}{2}-\alpha)}{\sin(\theta)}=\frac{\sqrt{1+h^2 n-h^2}}{n}\ge\frac{1}{n}$$

which implies the wanted result: $$\frac{\pi}{2}-\alpha\ge \frac{\theta}{n}$$

(it follows from $\sin(x)/x$ being monotonic and decreasing in $[0,\pi/2]$).