Header logo is

The Metric Nearness Problem




Metric nearness refers to the problem of optimally restoring metric properties to distance measurements that happen to be nonmetric due to measurement errors or otherwise. Metric data can be important in various settings, for example, in clustering, classification, metric-based indexing, query processing, and graph theoretic approximation algorithms. This paper formulates and solves the metric nearness problem: Given a set of pairwise dissimilarities, find a “nearest” set of distances that satisfy the properties of a metric—principally the triangle inequality. For solving this problem, the paper develops efficient triangle fixing algorithms that are based on an iterative projection method. An intriguing aspect of the metric nearness problem is that a special case turns out to be equivalent to the all pairs shortest paths problem. The paper exploits this equivalence and develops a new algorithm for the latter problem using a primal-dual method. Applications to graph clustering are provided as an illustratio n. We include experiments that demonstrate the computational superiority of triangle fixing over general purpose convex programming software. Finally, we conclude by suggesting various useful extensions and generalizations to metric nearness.

Author(s): Brickell, J. and Dhillon, IS. and Sra, S. and Tropp, JA.
Journal: SIAM Journal on Matrix Analysis and Applications
Volume: 30
Number (issue): 1
Pages: 375-396
Year: 2008
Month: April
Day: 0

Department(s): Empirical Inference
Bibtex Type: Article (article)

Digital: 0
DOI: 10.1137/060653391
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: Web


  title = {The Metric Nearness Problem},
  author = {Brickell, J. and Dhillon, IS. and Sra, S. and Tropp, JA.},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  volume = {30},
  number = {1},
  pages = {375-396},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  month = apr,
  year = {2008},
  month_numeric = {4}