# triangleFixing

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

##### 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)*