edmcr (version 0.2.0)

dpf: Dissimilarity Parameterization Formulation

Description

dpf returns a completed Euclidean Distance Matrix D, with dimension d, from a partial Euclidean Distance Matrix using the methods of Trosset (2000)

Usage

dpf(D, d, toler = 1e-08, lower = NULL, upper = NULL, retainMST = FALSE)

Arguments

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.

Value

D

The completed distance matrix with dimensionality d

optval

The minimum function value achieved during minimization (see details)

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.

References

Trosset, M.W. (2000). Distance Matrix Completion by Numerical Optimization.Computational Optimization and Applications, 17, 11<U+2013>22, 2000.

Examples

# NOT RUN {
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)

# }