nearCNSD: Nearest CNSD matrix

In CEGO: Combinatorial Efficient Global Optimization

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"
)

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.

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

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

See Also

nearPD, correctionCNSD, correctionDistanceMatrix

Examples

# 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

CEGO documentation built on May 29, 2024, 3:35 a.m.