Revision 1b3eb74607b471ab58965b6b645de315564b68f5 authored by Toni Giorgino on 18 May 2018, 04:47:54 UTC, committed by cran-robot on 18 May 2018, 04:47:54 UTC
1 parent d32f6f7
triangleFixing.Rd
\name{triangleFixing}
\alias{triangleFixing}
\alias{tri.ineq.show}
\title{Triangle Fixing algorithm for Metric Nearness}
\description{
Return the matrix satisfying the triangle inequality
most similar to a given input matrix.
}
\usage{
triangleFixing(D, tolerance=1e-15, max.iter=1e6)
tri.ineq.show(D)
}
\arguments{
\item{D}{the matrix to be fixed}
\item{tolerance}{threshold for convergence}
\item{max.iter}{iteration limit}
}
\value{
The fixed distance matrix (square symmetric).
}
\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 (\code{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 \code{tolerance} or the
\code{max.iter} iteration limit is reached.
The \code{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).
}
\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 \url{http://suvrit.de/work/soft/metricn.html}.
}
\seealso{
\code{\link[fossil]{tri.ineq}} in package \code{fossil}, which checks
whether a distance matrix respects the triangle inequality.
}
\examples{
%% dyn.load("src/dtw.so"); source("R/triangleFixing.R");
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)
}
\concept{Dissimilarity matrix}
\concept{Triangle inequality}
\author{Toni Giorgino}
\keyword{cluster}
Computing file changes ...