5
$\begingroup$

I have unit vectors in a high-dimensional space (~300) that are non-uniformly distributed over this hypersphere. There is physical meaning when the vectors are clustered together, but I'm hypothesizing that there is additional meaning when the vectors form a "path" along this hypersphere.

For the purposes of this question, let's assume that the deviation between the geodesic across the hypersphere and a straight line are are approximately equal (that is, I'm assuming the distances are small relative to the radius).

The question becomes, "From a large 300-dimensional point cloud in Euclidian space, how do I detect groups of points that are aligned in any direction?"

$\endgroup$
  • $\begingroup$ I have no idea how to solve this, but I'd love to hear someone explain it. And I'd REALLY love to know what those 300 variables represent, and what it means when they clump or build strings. $\endgroup$ – JRE Jun 15 '15 at 17:01
  • $\begingroup$ A shot in the dark: find a base for a subset of points. If the dimension of the base is "small", then in some sense the points in the subset are all in a hyperplane of the Euclidean space. I don't know how to choose the subsets, or how to indentfy points that are "close" to the hyperplane but not on it. $\endgroup$ – MBaz Jun 15 '15 at 17:14
  • 1
    $\begingroup$ Clustering in high dimensions is tricky due to the curse of dimensionality. I don't have practical experience with your problem, but I found a relevant paper: Clustering on the Unit Hypersphere using von Mises-Fisher Distributions. You should also be able to use a prior to incorporate the filament assumption. $\endgroup$ – Emre Jun 15 '15 at 17:21
  • $\begingroup$ Have you tried standard data clustering algorithms? Who knows, they might work well enough for your data. $\endgroup$ – Matt L. Jun 15 '15 at 17:44
  • $\begingroup$ @MattL. a clustering algorithm would only give me spots of high local density, it wouldn't give me points that are orientated, e.g. a sphere of points is the null, while a hyper-ellipsoid that points strongly in a few directions is what I'm looking for. $\endgroup$ – Hooked Jun 15 '15 at 17:49
2
$\begingroup$

Following my comment, I now have time to post it as an answer.
If you expect that a large enough portion of the vectors belong to that line, you can use RANSAC.
RANSAC works by selecting a small and random subset of the data and fit it to the desired model (say a line). The fitting can be achieved in any way you like, e.g. least-squares. Then, the data is divided to inliers (the points in space that "agree" with the model) and outliers (those who don't "agree"). The process is repeated until you have enough inliers.
This would only work if the probability of selecting the points on the line is high enough.

As far as multiple lines, I don't think RANSAC supports this inherently. You can do it iteratively by removing all inliers from the set once a line has been found.

If you are working in MATLAB\Octave, my favourite RANSAC implementation can be downloaded from here.

$\endgroup$
0
$\begingroup$

You know that in a two dimensional plane two points form a line why a simple equation holds namely - $y = mx + c$ put the other way if dimensions are $x1$ and $x2$ than for a line to exist, the equation $ a_1x_1 + a_2x_2 = C $ holds true for any value of $a_1$ and $a_2$ and $C$.

Generalizing this in an $N$ dimensional space, it is a line if $ a_1x_1 + a_2x_2 + .... a_nx_n = C $ holds true!

This of course gets hard exponentially as $N$ increases. So you may apply variety of search algorithms or dimensionality reduction algorithms. You can also use linear regression if you are seeing that large number of points are essentially lined up around a single line.

I hope I have understood and answered your question correctly! (still unsure though).

$\endgroup$
  • $\begingroup$ The heart of the question is how to effectively find the groups of points that would fit along (or close to) a line. It's infeasible to test all sets of points as my $N$ is large. $\endgroup$ – Hooked Jun 15 '15 at 18:06

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.