Header logo is ei

Triangle Fixing Algorithms for the Metric Nearness Problem

2005

Conference Paper

ei


Various problems in machine learning, databases, and statistics involve pairwise distances among a set of objects. It is often desirable for these distances to satisfy the properties of a metric, especially the triangle inequality. Applications where metric data is useful include clustering, classification, metric-based indexing, and approximation algorithms for various graph problems. This paper presents the Metric Nearness Problem: Given a dissimilarity matrix, find the "nearest" matrix of distances that satisfy the triangle inequalities. For lp nearness measures, this paper develops efficient triangle fixing algorithms that compute globally optimal solutions by exploiting the inherent structure of the problem. Empirically, the algorithms have time and storage costs that are linear in the number of triangle constraints. The methods can also be easily parallelized for additional speed.

Author(s): Dhillon, I. and Sra, S. and Tropp, J.
Book Title: Advances in Neural Information Processing Systems 17
Journal: Advances in Neural Information Processing Systems 17: Proceedings of the 2004 Conference
Pages: 361-368
Year: 2005
Month: July
Day: 0
Editors: Saul, L.K. , Y. Weiss, L. Bottou
Publisher: MIT Press

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: Eighteenth Annual Conference on Neural Information Processing Systems (NIPS 2004)
Event Place: Vancouver, BC, Canada

Address: Cambridge, MA, USA
Digital: 0
ISBN: 0-262-19534-8
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{5224,
  title = {Triangle Fixing Algorithms for the Metric Nearness Problem},
  author = {Dhillon, I. and Sra, S. and Tropp, J.},
  journal = {Advances in Neural Information Processing Systems 17: Proceedings of the 2004 Conference},
  booktitle = {Advances in Neural Information Processing Systems 17},
  pages = {361-368},
  editors = {Saul, L.K. , Y. Weiss, L. Bottou},
  publisher = {MIT Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Cambridge, MA, USA},
  month = jul,
  year = {2005},
  month_numeric = {7}
}