How to compare two distance matrices considering point permutation?

user_11491606 0
Viewed 89

I know how to compare two distance matrices if they order the points in the same way, but what if that is not guaranteed? Say we have 3 points n1, n2 and n3, and their distance matrix:

0 4 5
4 0 3
5 3 0

Then another set of points m1, m2 and m3 and their distance matrix:

0 3 4
3 0 5
4 5 0

If I directly compare the two matrices (e.g. using Mantel's test), those two would be quite different. But if we reorder the points, they are actually equivalent (n1 = m3, n2 = m1, n3 = m2).

So how can we compare two matrices considering this point permutation? A BF way is to try each permutation and take the highest similarity, but that would be O(n!).

For one-dimension case I found this solution: Given two arrays, find the permutations that give closest distance between two arrays. But I'm not sure how to use it in my case.

matrix algorithm python
1 Answers

We can rotate the matrix to look at only those combinations where the diagonal is zero. Since the rows and columns move as a whole, you only need to look at n combinations where n is the number of rows (or columns). Basically, when you rotate the matrix to move the 3rd row to the first row (for e.g.), all other moves are defined too.

Try this to get the combination of b that gives the least distance with a

def foo(a, b):
    n, _ = b.shape
    ans = b
    diff = np.abs(a - b).sum()
    for i in range(n):
        tmp = np.roll(b, i, (0, 1))
        tmp_diff = np.abs(a - tmp).sum()
        if tmp_diff < diff:
            diff = tmp_diff
            ans = tmp
    return ans, diff

# Usage
d1 = np.array([[0, 4, 5],
               [4, 0, 3],
               [5, 3, 0]])
d2 = np.array([[0, 3, 4],
               [3, 0, 5],
               [4, 5, 0]])

foo(d1, d2)
# (array([[0, 4, 5],
#         [4, 0, 3],
#         [5, 3, 0]]),
#  1)

In this example, the three combinations we checked are given by:

for i in range(3):
    print(np.roll(d2, i, (0, 1)), "\n")
# [[0 3 4]
#  [3 0 5]
#  [4 5 0]] 

# [[0 4 5]
#  [4 0 3]
#  [5 3 0]] 

# [[0 5 3]
#  [5 0 4]
#  [3 4 0]]
user_71289340
Related