4
$\begingroup$

I have a set of points defined by their coordinates $(x_1,y_1)$ after changing some parameters of the problem I obtain a second set of points defined by their coordinates $(x_2, y_2)$. There exists a one-to-one mapping between these two sets of points. Is there a standard way to obtain the most likely mapping between these two sets of points? Consider the following sets of points: (blue, red, and green are different sets)

3 sets of points.

I would like to obtain this mapping from blue to red to green: 3 sets of points with the correct mapping shown.

My first thought for solving this is to compute the nearest neighbor of blue points to each of the red points, sort these nearest neighbors by distance, remove the closest match, recompute the nearest neighbors, and repeat. However, it is easy to think of situations for which this algorithm does not work. (I don't think it works for the sets of points above.)

Background:

I'm solving a large eigenvalue problem and attempting to track eigenvalues as I vary parameters.

$\endgroup$
  • $\begingroup$ What happens if you just identify them by magnitude? I have seen people track what happens to the smallest eigenvalue as they vary a parameter, you could try the same with second smallest etc. $\endgroup$ – Andrew T. Barker Jul 23 '14 at 3:39
  • 1
    $\begingroup$ I'm not an expert, but let me mention that there are matrix perturbation theories. $\endgroup$ – AlexE Jul 23 '14 at 12:30
  • $\begingroup$ This sounds like Iterative Closest Point by Besl and McKay: en.wikipedia.org/wiki/Iterative_closest_point $\endgroup$ – André Jul 24 '14 at 11:49
2
$\begingroup$

One thing to try is this modification of your idea:

for x in blue-points:
  for y in red-points, sorted by distance to x:
    find all green points z "close enough" to y + (y-x)
    if angle between vectors (y-x) and (z-y) is "small enough":
      return (x,y,z) as the guess

Basically, you can try to use your suspicion that the points move along smooth curves at roughly ("locally") constant velocities. Any smooth curve is approximately close to a line, and the angle between consecutive chords of the curve is likely to be small. In your plot, "small enough" angle might mean something like $<30^\circ$.

This is not specific to eigenvalues; you could do the same thing for roots of polynomials with time-varying coefficients (which are also easier to test with). With very many points you'll need a clever data structure to implement this efficiently, but you don't seem to have many.

Another mathematical justification for doing this is that the angle between chords is related to the curvature of a curve (as in the Frenet-Serret formulas). So in some sense this approach tries to minimize or bound the curvature of the curves that it finds.

$\endgroup$
  • $\begingroup$ @OSE, if your problem is a reasonably smooth function of your parameters, you may gain more insight with pertubation theories, cmp. e.g. en.wikipedia.org/wiki/Eigenvalue_perturbation $\endgroup$ – AlexE Jul 25 '14 at 11:09
  • $\begingroup$ @AlexE The wikipedia page shows an example for symmetric and positive definite matrices, do you know if there are similar theories for general matrices? $\endgroup$ – OSE Jul 25 '14 at 15:41

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.