Generate Random Sparse Vectors at a Given Distance on the Unit Hypersphere

Question

I'm trying to write a Python function that would take 3 parameters: n: Number of dimensions s: Sparsity factor (example 0.9) d: Distance

The function would return two vectors in n dimensions that are on the unit hypersphere at distance "d" and they are both sparse.

The distance can be euclidean (0..2) or angular (0..Pi) it doesn't matter.

Thanks a lot for your help! Luis.

Answer 1

Randomly select the members you wish to be non-zero:

from random import random, gauss

n = 1000
s = 0.1
d = 10 # distance between two points
non_zero = []
for i in range(n):
    if random() < s:
        non_zero.append(i)

Then sample a point on the sphere in len(non_zero) dimensions (see mathoverflow).

v = [gauss() for i in non_zero]
mag = sum(x**2 for x in v)**(0.5)
v = [x / mag for x in v]

Put it back into the original space

w = [0 for _ in range(d)]
for i, x in zip(non_zero, v):
    w[i] = x
print w

We now need a point $z$ which satisfies

• $|z| = 1$
• $|z - w| = d$
• $z$ is sparse.

Retraction:

I am leaving this partial solution because it might help someone else. But this problem doesn't seem amenable to generating one point, then the second. If $d$ is really small (and we are considering Euclidean distances), then the second vector must be non-zero in every coordinate where the first, ruining its sparseness. If $d$ is angular and small, then $\frac{w \cdot z}{|w||z|} = w \cdot z = \cos(d)$ is nearly 1, and the non-zero coordinates of $w$ must be non-zero in $z$ as well.

Edits:

• Added distance $d = 10$.
• Changed variable names to agree with OP's.
• Removed scaling $w$
• Added Retract.