English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  The Metric Nearness Problem

Brickell, J., Dhillon, I., Sra, S., & Tropp, J. (2008). The Metric Nearness Problem. SIAM journal on matrix analysis and applications, 30(1), 375-396. doi:10.1137/060653391.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-C9D5-C Version Permalink: http://hdl.handle.net/21.11116/0000-0003-3128-9
Genre: Journal Article

Files

show Files

Locators

show
hide
Locator:
https://epubs.siam.org/doi/10.1137/060653391 (Publisher version)
Description:
-

Creators

show
hide
 Creators:
Brickell, J, Author
Dhillon, I1, 2, Author              
Sra, S1, 2, Author              
Tropp, JA, Author
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497794              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s):
 Dates: 2008-04
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1137/060653391
BibTex Citekey: 5124
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: SIAM journal on matrix analysis and applications
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Philadelphia, Pa. : The Society
Pages: - Volume / Issue: 30 (1) Sequence Number: - Start / End Page: 375 - 396 Identifier: ISSN: 0895-4798
CoNE: https://pure.mpg.de/cone/journals/resource/954928546249