nearCNSD: Nearest CNSD matrix

Description

This function implements the alternating projection algorithm by Glunt et al. (1990) to calculate the nearest conditionally negative semi-definite (CNSD) matrix (or: the nearest Euclidean distance matrix). The function is similar to the nearPD function from the Matrix package, which implements a very similar algorithm for finding the nearest Positive Semi-Definite (PSD) matrix.

Usage

nearCNSD(
  x,
  eig.tol = 1e-08,
  conv.tol = 1e-08,
  maxit = 1000,
  conv.norm.type = "F"
)

Value

list with:

mat: nearestCNSD matrix
normF: F-norm between original and resulting matrices
iterations: the number of performed
rel.tol: the relative value used for the tolerance convergence criterion
converged: a boolean that records whether the algorithm

Arguments

x: symmetric matrix, to be turned into a CNSD matrix.
eig.tol: eigenvalue torelance value. Eigenvalues between -tol and tol are assumed to be zero.
conv.tol: convergence torelance value. The algorithm stops if the norm of the difference between two iterations is below this value.
maxit: maximum number of iterations. The algorithm stops if this value is exceeded, even if not converged.
conv.norm.type: type of norm, by default the F-norm (Frobenius). See norm for other choices.

References

Glunt, W.; Hayden, T. L.; Hong, S. and Wells, J. An alternating projection algorithm for computing the nearest Euclidean distance matrix, SIAM Journal on Matrix Analysis and Applications, SIAM, 1990, 11, 589-600

Examples

Run this code

# example using Insert distance with permutations:
x <- list(c(2,1,4,3),c(2,4,3,1),c(4,2,1,3),c(4,3,2,1),c(1,4,3,2))
D <- distanceMatrix(x,distancePermutationInsert)
print(D)
is.CNSD(D)
nearD <- nearCNSD(D)
print(nearD)
is.CNSD(nearD$mat)
# or example matrix from Glunt et al. (1990):
D <- matrix(c(0,1,1,1,0,9,1,9,0),3,3)
print(D)
is.CNSD(D)
nearD <- nearCNSD(D)
print(nearD)
is.CNSD(nearD$mat)
# note, that the resulting values given by Glunt et al. (1990) are 19/9 and 76/9