/sci/ - Science & Math

[Anonymous No.6739180]

Is there a computationally efficient method of finding the great circle distance? What about for a hypercube?

[Anonymous No.6739198]

<span class="math">d(P,Q)= \alpha (P,Q) r[/spoiler]

[Anonymous No.6739205]

>>6739198
Sorry. I meant I wanted to approximate. And I don't know why I wrote hypercube. I meant hypersphere. Also, the all the points are on the unit (hyper-)sphere and specified by their angles. (e.g. inclination and declination on the 2-Sphere.)

[Anonymous No.6739211]

on the unit sphere (any dimension), can't you just find the inner product and then take the inverse cosine of that?

[Anonymous No.6739220]

>>6739211
Yes! The problem with that is I need to convert from spherical to rectangular coordinates to calculate the dot product. This requires <span class="math">O(d^2)[/spoiler] operations in the dimensionality of the hypersphere. In 3D I'm clocking a slow down of a factor of about 8 compared with not doing the conversion. In, say, 600 dimensions, a roughly <span class="math">100^2[/spoiler] fold slow down is expected.

[Anonymous No.6739237]

>>6739205

Why approximate when the exact solution is a simple linear computation?

[Anonymous No.6739246]

>>6739237
Because the computation I described in >>6739220 is inefficient. I'm calculating the distance a lot in my program, so it's the weakest link.

The alternative is to store Cartesian coordinate and calculate the euclidean distance, but I'd prefer not to go down that road if I can calculate the great circle distance in linear time.

[Anonymous No.6739561]

So, I'm a complete novice at coding, so perhaps this question is moronic, but why aren't you already storing things in Cartesian? Which system are you using instead?

[Anonymous No.6739586]

>>6739561
I think he says he is using spherical coordinates, i.e. a bunch of angles. So to get to Cartesian from that, he needs to calculate a bunch of sines and cosines, and multiply them together. That's slow.

OP, I think you are out of luck. Is there an advantage for you to be using spherical coordinates rather than Cartesian to begin with?

[Anonymous No.6739588]

600D spheres
what are you upto OP

[Anonymous No.6739591]

>>6739586

Yeah, I figured spherical was the only possible alternative, but I can't for the life of me imagine why that would be. In addition to making things like the dot product harder to calculate, it's harder to generalize to n-dimensions like in the hypersphere.

[Anonymous No.6739613]

>>6739591
600 dimensional spheres would be no problem with Cartesian coordinates, if all you need is a collection of points. There might be the need to re-normalize your vector now and then, but that's far less pain then spherical in N-D.

[Anonymous No.6740371]

>>6739561
>Which system are you using instead?
I'm just using the transforms from here: https://en.wikipedia.org/wiki/N-sphere#Spherical_coordinates

>>6739586
>Is there an advantage for you to be using spherical coordinates rather than Cartesian to begin with?
I want to be able to rotate the points along the surface of the sphere. Doing that is just addition if you store spherical coordinates. But as we've seen it creates problems computing distance.

>>6739588
Trying to apply a variation of the Thomson problem to a problem in distributional semantics. The makers of word2vec (Google it) had good results with 600-D spheres, so that's very roughly what I'm anticipating will be good for what I'm doing.

>>6739613
>>6739591 Isn't me.
>There might be the need to re-normalize your vector now and then
Yep. That's just what I'm going to do now, I think. One of the reasons I was trying to avoid it was that adding to an element in the vector then normalising does rotate the vector, but biases that rotation to the corner of the cube surrounding the sphere (in 3D). There's also a linear-time performance penalty just for rotating the vector in that way which I was trying to avoid.

[Anonymous No.6740376]

>>6740371
>the corner
should be "one of the corners" or something like that. derp

[Anonymous No.6740841]

>>6740371
>adding to an element in the vector then normalising does rotate the vector

There are faster and more accurate methods for rotating an n-d vector. You can pick two elements and apply a 2-D rotation to them, for example. Or, if u is a unit vector, apply the transformation (I-2*u*u') to another unit vector v. This reflects v through the plane perpendicular to u, and requires D*2 multiplications.

You can easily rotate a unit vector v towards another unit vector u as well.

I guess it depends on where your rotations are coming from. What kind of rotations do you need?

[Anonymous No.6740877]

>>6740841
>(I-2*u*u')
That's a matrix, right? Wouldn't computing the matrix itself required more than D*2 operations?

>I guess it depends on where your rotations are coming from. What kind of rotations do you need?
My initial idea was to rotate the vectors in the direction of a torque applied to them, but what I'm doing now is simpler and yields acceptable results. I'm just adding to the vector and normalising, like I said. I think it works out alright in terms of accuracy because I'm only adding small amounts at a time. The only way this method could be improved in my application is by having a sub-linear time rotation method.

Also, sub-linear methods of finding euclidean distance would be breddy gud

[Anonymous No.6740889]

It looks like Wikipedia actually gives a method for computing this in spherical coordinates:
http://en.wikipedia.org/wiki/Great-circle_distance

[Anonymous No.6740895]

>>6740889
Needs moar computational efficiency

[Anonymous No.6740931]

>>6740877
If you wrote it all out, I-2*u*u' would be a matrix, but there is no need to do that. Just calculate v-2*u*(u'*v). That's one inner product, a scaling, and a subtraction.

To rotate v towards u....
Suppose u and v are non-colinear unit vectors, and you want to rotate v towards u by t radians.
Set:
w=u-(u'*v)*v
x=w/|w| ( so x is a unit vector )
y=cos(t)*v+sin(t)*x
Then y is the vector you are after, i.e. it is what you get if you rotate v t radians towards u.

[Anonymous No.6740961]

>>6740931
>Just calculate v-2*u*(u'*v)
That's easy for me to do, but the computer will still have to do all that work. (Correct me if you think I'm missing something.) That works out to a similar amount of work as this >>6739220

>To rotate v towards u....
This works in > 3 dimensions? Is there a name for this that I could google?

[Anonymous No.6740984]

>>6740961
Multiplying a vector times an NxN matrix will generally take N^2 multiplications, but this
v-2*u*(u'*v) would only take 2*N multiplications.

Yes, in all dimensions.

In the special case that u is one of the
standard basis vectors:
e=(0,...,0,1,0,...,0)
[say the k-th element is 1]
you can rotate a unit vector
v by t radians towards e
along a great circle to get y: Set
h=sin(t)/sqrt(1-v_k^2)
y=(cos(t)-h*v_k)*v+h*e

This gives the exact answer for any t.
Of course you wouldn't actually
calculate h*e in code and add it,
just increase a k-th component of
the first term by h. It won't work
if v=e or v=-e, then the
direction of rotation is not well-defined.

I think what you are after is popularly referred to as Slerp.
http://en.wikipedia.org/wiki/Slerp

[Anonymous No.6741006]

>>6740984
>2*N multiplications
>http://en.wikipedia.org/wiki/Slerp
You're helpful as fuck