0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Andrew D. Hwang Jan 1 '17 at 20:58
  • $\begingroup$ 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. $\endgroup$ – user3635284 Jan 1 '17 at 21:13
  • $\begingroup$ And I would like the vectors to be uniformly random on the unit hypersphere. $\endgroup$ – user3635284 Jan 1 '17 at 21:14
1
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This creates a single point in the sphere, I need two random points at a given distance. $\endgroup$ – user3635284 Jan 2 '17 at 16:09
  • $\begingroup$ @user3635284 do you need two points on the sphere? Then run it twice. Are you looking for two points which for an equilateral triangle with the origin? $\endgroup$ – yberman Jan 2 '17 at 18:19
  • 1
    $\begingroup$ As I understand the OP, distance to the origin = 1 (since they are in the unit hypersphere), parameter d is distance between the vectors. $\endgroup$ – cladelpino Jan 2 '17 at 18:25

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.