mstLB Returns an nxn matrix containing the lower bounds for all unknown entries
in the partial distance matrix D such that the minimum spanning tree of the partial matrix D
is preserved upon completion.
mstLB(D)
| D | An nxn partial distance matrix to be completed |
|---|
Returns an nxn matrix containing the lower bound for the unknown entries in D
The insight in constructing the lower bound is drawn from single-linkage clustering. Every edge in a spanning tree separates the vertices into two different groups, depending on which points remain connected to either one vertex or the other of that edge. Because the tree is a minimum spanning tree, if we select the largest edge, then the distance between any vertex of one group and any vertex of the other group must be at least as large as that of the the largest edge. This gives a lower bound for these distances that will preserve that edge in the minimum spanning tree. The same reasoning is applied recursively to each separate group, thus producing a lower bound on all edges.
The details of the algorithm can be found in Rahman & Oldford (2016).
Rahman, D., & Oldford R.W. (2016). Euclidean Distance Matrix Completion and Point Configurations from the Minimal Spanning Tree.
D <- matrix(c(0,3,4,3,4,3, 3,0,1,NA,5,NA, 4,1,0,5,NA,5, 3,NA,5,0,1,NA, 4,5,NA,1,0,5, 3,NA,5,NA,5,0),byrow=TRUE, nrow=6) mstLB(D)#> [,1] [,2] [,3] [,4] [,5] [,6] #> [1,] 0 3 3 3 3 3 #> [2,] 3 0 1 3 3 3 #> [3,] 3 1 0 3 3 3 #> [4,] 3 3 3 0 1 3 #> [5,] 3 3 3 1 0 3 #> [6,] 3 3 3 3 3 0