1
$\begingroup$

Given:

  • an $n$-dimensional vector $v = (v_1,\ldots,v_n) \in \mathbb{R}^n$
  • an angle $\theta \in (0, \frac{\pi}{2})$

I am looking for a technique to construct a vector $w = (w_1,\ldots, w_n) \in \mathbb{R}^n$ such that:

$$\frac{v\cdot w}{\|v\|\|w\|} = \cos(\theta)$$

I am specifically interested in a way to do this for $n > 3$ dimensions (for $n \leq 3$, I think you could do it with rotation matrices).

I realize that when $n \geq 3$, there are an infinite number of feasible vectors $w$. I would be OK with any $w$ that satisfies the following criteria:

  1. $v$ and $w$ are distinct: $v_i \neq w_i$ for all $i$.

  2. all components of $w$ are non-zero: $w_i \neq 0$ for all $i$.

$\endgroup$
  • $\begingroup$ How do you define the angle in $\mathbb R^n$ ? $\endgroup$ – Youem Apr 13 '18 at 3:07
  • $\begingroup$ How would you satisfy your criteria if $v = (1,0,0)$ and $\theta = \pi/ 2$ ? $\endgroup$ – Youem Apr 13 '18 at 3:17
  • $\begingroup$ @Youem I don't have an intuitive definition for the angle in $\mathbb{R}^n$. It should just be any vector $w$ such that the cosine similarity is $\cos(\theta)$. $\endgroup$ – Elements Apr 13 '18 at 3:18
  • $\begingroup$ okay I understand your definition of the angle but you criteria is not always doable $\endgroup$ – Youem Apr 13 '18 at 3:19
0
$\begingroup$

A "just wing it" algorithm which I think would be numerically stable is

  • Find a nonzero vector $u$ that is perpendicular to $v$, for example $$ u=(0,\ldots,0,v_j,0,\ldots,0,-v_i,0,\ldots,0)$$ where $v_i$ and $v_j$ are the numerically largest coordinates of $v$.

  • Normalize $u$ so its norm equals $\|v\|$.

  • Take $w=\cos(\theta)v+\sin(\theta)u$.

Note that $w$ does not depend continuously on $v$, but that is impossible when $n$ is odd, due to the hairy ball theorem. For even $n$ you can get continuity by taking $$ u = (v_2,-v_1,v_4,-v_3,\ldots) $$


If it's important to you to make all elements of $w$ nonzero, instead choose all elements of $u$ except one randomly (with some continuous distribution). Let the one you don't choose randomly correspond to the numerically largest coordinate of $v$; then you can easily solve for the value of that coordinate that will make $u\cdot v=0$.

Then each element of $ w $ will almost surely be nonzero.

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

I'm adding another solution (credit goes to one of the PhD students in my lab), since I found it elegant / wanted to post some code for others.


Solution:

Given $v$, we want to find a $w$ such that:

$$\frac{v.w}{\|v\|\|w\|} = \cos(\theta)$$

For clarity of exposition, let's assume that $\|v\| =1$ and $\|w\| = 1$ (if $v$ is not normalized, then normalize it). We can now express our required condition as:

$$v.w = \cos(\theta)$$

We will construct a suitable vector as $$w = U.r$$ where:

  • $U = [\, v \,|\, u_2 \,|\, \ldots \,|\,u_n] \in \mathbb{R}^{n\times n}$ is an orthonormal matrix with $v$ in the first column. We can construct this matrix given $v$ by using the Gram-Schmidt process to determine the remaining basis vectors $u_2,\ldots, u_d$.

  • $r = (r_1, r_2, \ldots, r_d) \in \mathbb{R}^n$ is a unit vector where $r_1 = \cos(\theta)$ and $\|r\| = 1$

To see that these choices of $U$ and $r$ produce a suitable $w$, note:

$$\begin{align} v.w &= v.(Ur)\\ &= v.(u_1.r_1 + u_2.r_2, \ldots, u_d. r_d)\\ &= (v.u_1) r_1 + (v.u_2)r_2 + \ldots + (v.u_d)r_d\\ \end{align}$$ By construction of $U$, we have that $u_1 = v$ and $v.u_i = 0$ for $i = 2,\ldots, n$, so: $$\begin{align} (v.u_1) r_1 + (v.u_2)r_2 + \ldots + (v.u_d)r_d = \|v\|^2 r_1 = r_1 \end{align}$$ Since we have set $r_1 = \cos(\theta)$, we therefore have that: $$\frac{v.w}{\|v\|\|w\|} = r_1 = \cos(\theta)$$ as desired.

Note that we are not quite done, since we still have choose $r_2,\ldots, r_d$ so that $\|r\| = 1$. This requires: $$ \begin{align} \|r\| &= 1\\ {r_1}^2 + {r_2}^2 + \ldots + {r_n}^2 &= 1\\ \cos^2(\theta) + {r_2}^2 + \ldots + {r_n}^2 &= 1\\ {r_2}^2 + \ldots + {r_n}^2 &= 1 - \cos^2(\theta) \\ {r_2}^2 + \ldots + {r_n}^2 &= \sin^2(\theta) \end{align} $$ In other words, $r_2,\ldots, r_n$ must lie on the surface of a $n$-dimensional sphere with radius $\sin(\theta)$. While there are many ways to choose these values, one easy way is to sample this point uniformly from the surface of the sphere. Based on this post, this can be achieved by sampling a $n -1$ random variables $r_i \sim N(0,1)$ and scaling them so that their norm is exactly $\sin(\theta)$


Code:

import numpy as np
from numpy.linalg import norm

def rotate_vector(v, angle):

    """
    returns vector w such that |w|=|v| and v.w/|v||w| = cos(angle) and 
    :param v: numpy array with dimension d >= 2
    :param angle: angle of rotation in radians 
    :return: w, numpy array of dimension v.dim
    """

    assert isinstance(v, np.ndarray)
    assert np.all(np.isfinite(v)) and v.ndim == 1 and len(v) >= 2
    norm_value = norm(v)
    d = len(v)

    # normalize vector
    v = v / norm(v)

    # construct orthonormal matrix U where U[:, 0] = v
    while True:
        u_diag = np.random.randn(d)
        if not np.any(np.isclose(u_diag, 0.0, atol = 0.01)):
            break

    U = np.diag(u_diag)
    U[:, 0] = v
    U, _ = np.linalg.qr(U)
    assert np.all(np.isclose(np.abs(U[:, 0]), np.abs(v)))

    # overcases cases where U flips the sign
    if np.all(np.isclose(U[:, 0], -v)):
        U = -U

    # generate a vector r = [r_1, r_2, .., .. r_d ]
    # r = cos(angle)
    # r_2,..., r_d are any non-zero values such that (r_2)^2 + ... + (r_d)^2 = sin^2(alpha)

    # r_2,..,r_d is just a point on a d-1 dimensional sphere with radius sin(alpha)
    # this can be sampled uniformly using a multivariate gaussian
    # see https://math.stackexchange.com/a/1585996/7145
    while True:
        z = np.random.randn(d-1)
        if not np.any(np.isclose(z, 0.0, atol = 0.01)):
            break

    r = np.sin(angle) * (z / norm(z))
    r = np.insert(r, 0, np.cos(angle))

    # compute rotated unit vector
    w = np.dot(U, r)
    assert np.isclose(norm(w), 1.0)
    assert np.isclose(angle, np.arccos(np.dot(v, w)))

    # rescale vector with the same norm as original input
    w = w * norm_value
    return 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.