triangleFixing

0th

Percentile

Triangle Fixing algorithm for Metric Nearness

Return the matrix satisfying the triangle inequality most similar to a given input matrix.

Keywords
cluster
Usage
triangleFixing(D, tolerance=1e-15, max.iter=1e6)
tri.ineq.show(D)
Arguments
D

the matrix to be fixed

tolerance

threshold for convergence

max.iter

iteration limit

Details

Given a symmetric matrix, returns the symmetric matrix "most similar" to it that satisfies the triangle inequality. (Similarity is measured in the L2 sense.) This is an implementation of the L2 triangle fixing algorithm for metric nearness (Metric_Nearness_L2) given in [1] and [2].

WARNING: the algorithm does not seem to work in all cases.

The input should be a symmetric matrix (or dist object, which is coerced). Convergence of the iterative algorithm is assumed when total matrix element change is less than tolerance or the max.iter iteration limit is reached.

The tri.ineq.show function checks whether a dissimilarity matrix respects the triangle inequality. Returns NULL if it does, or a Nx3 matrix of indices where it doesn't (unsorted).

Value

The fixed distance matrix (square symmetric).

References

1. Brickell, J., Dhillon, I., Sra, S., Tropp, J. (2008). The Metric Nearness Problem. SIAM. J. Matrix Anal. & Appl. 30, 375-396.

2. S. Sra, "METRIC: The Metric Nearness Problem" code at http://suvrit.de/work/soft/metricn.html.

See Also

tri.ineq in package fossil, which checks whether a distance matrix respects the triangle inequality.

Aliases
  • triangleFixing
  • tri.ineq.show
Examples
# NOT RUN {
<!-- %% dyn.load("src/dtw.so"); source("R/triangleFixing.R");  -->
# }
# NOT RUN {
a<-matrix(0.2, 4,4)
a[4,2]<-0.8
a<-as.matrix(as.dist(a))
af<-triangleFixing(a)

tri.ineq.show(a)
stopifnot(tri.ineq.show(af)==NULL)

## Example in http://suvrit.de/work/soft/metricn.html
a<-matrix(c(0, 3, 7,
            3, 0, 1,
            7, 1, 0),3)
af<-triangleFixing(a)

tri.ineq.show(a)
stopifnot(tri.ineq.show(af)==NULL)

# }
Documentation reproduced from package dtw, version 1.20-1, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.