dpf returns a completed Euclidean Distance Matrix D, with dimension d,
from a partial Euclidean Distance Matrix using the methods of Trosset (2000)
dpf(D, d, toler = 1e-08, lower = NULL, upper = NULL, retainMST = FALSE)
| D | An nxn partial-distance matrix to be completed. D must satisfy a list of conditions (see details), with unkown entries set to NA |
|---|---|
| d | The dimension for the resulting completion. |
| toler | The convergence tolerance of the algorithm. Set to a default value of 1e-8 |
| lower | An nxn matrix containing the lower bounds for the unknown entries in D. If NULL, lower is set to be a matrix of 0s. |
| upper | An nxn matrix containing the upper bounds of the unknown entries in D. If NULL, upper[i,j] is set to be the shortest path between node i and node j. |
| retainMST | D logical input indicating if the current minimum spanning tree structure in D should be retained. If TRUE, a judicious choice of Lower is calculated internally such that the MST is retained. |
The completed distance matrix with dimensionality d
The minimum function value achieved during minimization (see details)
This is an implementation of the Dissimilarity Parameterization Formulation (DPF) for Euclidean Distance Matrix Completion, as proposed in 'Distance Matrix Completion by Numerical Optimization' (Trosset, 2000).
The method seeks to minimize the following:
$$\sum_{i=1}^{d}(\lambda_{i} - \lambda_{max}) + \sum_{i=d+1}^{n}\lambda_{i}^{2}$$
where \(\lambda_{i}\) are the ordered eigenvalues of \(\tau(\Delta)\). For details, see Trosset(2000)
The matrix D is a partial-distance matrix, meaning some of its entries are unknown. It must satisfy the following conditions in order to be completed:
diag(D) = 0
If \(a_{ij}\) is known, \(a_{ji} = a_{ij}\)
If \(a_{ij}\) is unknown, so is \(a_{ji}\)
The graph of D must be connected. If D can be decomposed into two (or more) subgraphs, then the completion of D can be decomposed into two (or more) independent completion problems.
Trosset, M.W. (2000). Distance Matrix Completion by Numerical Optimization.Computational Optimization and Applications, 17, 11–22, 2000.
set.seed(1337) 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) edmc(D, method="dpf", d=3, toler=1e-8)#> $D #> [,1] [,2] [,3] [,4] [,5] [,6] #> [1,] 0 3.000000 4.000000 3.000000 4.000000 3.00000 #> [2,] 3 0.000000 1.000000 4.242738 5.000000 4.24788 #> [3,] 4 1.000000 0.000000 5.000000 5.656735 5.00000 #> [4,] 3 4.242738 5.000000 0.000000 1.000000 4.24077 #> [5,] 4 5.000000 5.656735 1.000000 0.000000 5.00000 #> [6,] 3 4.247880 5.000000 4.240770 5.000000 0.00000 #> #> $optval #> [1] 1.23048e-09 #>