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

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.

• By "sparsity factor" do you mean something like "the fraction of entries that are non-zero"? Do you want these vectors to be chosen "randomly"? If so, with respect to what probability measure on the sphere? – Andrew D. Hwang Jan 1 '17 at 20:58
• I meant the sparsity factor as the fraction of zeros, but it doesn't matter which way you take it. Either 90% of zeros or 10% of zeros is the same for the application, you just put the number you need to use. – user3635284 Jan 1 '17 at 21:13
• And I would like the vectors to be uniformly random on the unit hypersphere. – user3635284 Jan 1 '17 at 21:14

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$