Triangle Fixing Algorithms for the Metric Nearness Problem

Dhillon, I; Sra, S; Tropp, J

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Triangle Fixing Algorithms for the Metric Nearness Problem

MPS-Authors

There are no MPG-Authors in the publication available

External Resource

http://papers.nips.cc/paper/2598-triangle-fixing-algorithms-for-the-metric-nearness-problem.pdf
(出版社版)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Dhillon, I., Sra, S., & Tropp, J. (2005). Triangle Fixing Algorithms for the Metric Nearness Problem. In L., Saul, Y., Weiss, & L., Bottou (Eds.), Advances in Neural Information Processing Systems 17 (pp. 361-368). Cambridge, MA, USA: MIT Press.

引用: https://hdl.handle.net/11858/00-001M-0000-0013-D531-C

要旨

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.