Nonparametric Position Formulation

Source: R/npf.R

npf returns a completed Euclidean Distance Matrix D, with dimension d, from a partial Euclidean Distance Matrix using the methods of Fang & O'Leary (2012)

npf(
  D,
  A = NA,
  d,
  dmax = (nrow(D) - 1),
  decreaseDim = 1,
  stretch = NULL,
  method = "Linear",
  toler = 1e-08
)

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.
A

a weight matrix, with \(h_{ij} = 0\) implying \(a_{ij}\) is unknown. Generally, if \(a_{ij}\) is known, \(h_{ij} = 1\), although any non-negative weight is allowed.
d

the dimension of the resulting completion
dmax

the maximum dimension to consider during dimension relaxation
decreaseDim

during dimension reduction, the number of dimensions to decrease each step
stretch

should the distance matrix be multiplied by a scalar constant? If no, stretch = NULL, otherwise stretch is a positive scalar
method

The method used for dimension reduction, one of "Linear" or "NLP".
toler

convergence tolerance for the algorithm

Value

D

an nxn matrix of the completed Euclidean distances

optval

the minimum value achieved of the target function during minimization

Details

This is an implementation of the Nonconvex Position Formulation (npf) for Euclidean Distance Matrix Completion, as proposed in 'Euclidean Distance Matrix Completion Problems' (Fang & O'Leary, 2012).

The method seeks to minimize the following:

$$||A \cdot (D - K(XX'))||_{F}^{2}$$

where the function K() is that described in gram2edm, and the norm is Frobenius. Minimization is over X, the nxp matrix of node locations.

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.

See also

gram2edm

Examples


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)
             
A <- matrix(c(1,1,1,1,1,1,
             1,1,1,0,1,0,
             1,1,1,1,0,1,
             1,0,1,1,1,0,
             1,1,0,1,1,1,
             1,0,1,0,1,1),byrow=TRUE, nrow=6)

edmc(D, method="npf", d=3, dmax=5)

#> For consistency with the rest of the package the inequality sign may be switched from >= to <= in a future nloptr version.
#> $D
#>          [,1]     [,2]     [,3]     [,4]     [,5]     [,6]
#> [1,] 0.000000 3.000002 3.999999 3.000002 3.999999 3.000000
#> [2,] 3.000002 0.000000 1.000015 4.245940 5.000000 4.241093
#> [3,] 3.999999 1.000015 0.000000 5.000000 5.652452 5.000000
#> [4,] 3.000002 4.245940 5.000000 0.000000 1.000015 4.241094
#> [5,] 3.999999 5.000000 5.652452 1.000015 0.000000 5.000000
#> [6,] 3.000000 4.241093 5.000000 4.241094 5.000000 0.000000
#> 
#> $optval
#> [1] 4.278034e-09
#> 
#> [[3]]
#>               [,1]       [,2]        [,3]
#> [1,] -4.478872e-09  0.9013628  1.47006832
#> [2,]  2.122970e+00 -0.6821442  0.06098534
#> [3,]  2.826226e+00 -1.2152075 -0.40944498
#> [4,] -2.122970e+00 -0.6821443  0.06098548
#> [5,] -2.826226e+00 -1.2152073 -0.40944511
#> [6,]  1.248059e-07  2.8933406 -0.77314905
#>