1
$\begingroup$

I have two sets of points and I find with different methods, different correspondence matrices which shows which point in one set correspond to other point in the other set. How could I find the optimal correspondence matrix in order to minimize the distance between two sets of points from having both these matrices in hand?!!

**The correspondences are shown by arrows:**

enter image description here

For instance, if there is seven points in one set and four points in the other set, then the correspondence matrix that relates points in x-y space, might look like this

enter image description here

BTW, each of the correspondence matrices have just zero and one entries which shows which point corresponds to other point. Thanks in advance

Improve this question
$\endgroup$
7
  • $\begingroup$ First, please show how a correspondence matrix of yours looks like. Second, what are these plots and how to understand them? $\endgroup$
    – ttnphns
    Oct 3, 2014 at 19:49
  • $\begingroup$ @ttnphns the plots are a set of points in x-y plane. $\endgroup$
    – Dalek
    Oct 3, 2014 at 20:01
  • $\begingroup$ What do you mean by an "optimal" correspondence matrix? One which minimizes sum of squared distances between the correspondent points? $\endgroup$
    – user31264
    Oct 3, 2014 at 20:08
  • $\begingroup$ @user31264 the matrix that minimizes the distance between the points with the correspondence in the other set. $\endgroup$
    – Dalek
    Oct 3, 2014 at 20:11
  • $\begingroup$ If you have n rectangular similarity matrices (between the same two sets of items in all n cases) you may use Multidimensional Unfolding (MDU) technique in individual scaling (INDSCAL) regime to embed the points of both sets in a low dimensional Euclidean space. $\endgroup$
    – ttnphns
    Oct 4, 2014 at 8:49

1 Answer 1

Reset to default
1
$\begingroup$

Your problem is equivalent to the assignment problem, solved by a hungarian algorithm, and here is the correspondence:

  • points in the set 1 are agents
  • points in the set 2 are tasks
  • distances (or squared distances) are cost matrix
Improve this answer
$\endgroup$
2
  • $\begingroup$ If the cost matrix is binary, its assignment solving is elementary and actually doesn't need Hungarian algorithm. $\endgroup$
    – ttnphns
    Oct 3, 2014 at 21:15
  • $\begingroup$ @ttnphns - the cost matrix is distances between points, so it is not binary. The matrix in the text is an example of the assignment matrix. $\endgroup$
    – user31264
    Oct 4, 2014 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.