Brickell, Justin and Dhillon, Inderjit S. and Sra, Suvrit and Tropp, Joel A. (2008) The Metric Nearness Problem. SIAM Journal on Matrix Analysis and Applications, 30 (1). pp. 375396. ISSN 08954798. http://resolver.caltech.edu/CaltechAUTHORS:20110513152152857

PDF
 Published Version
See Usage Policy. 306Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110513152152857
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, metricbased 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 primaldual method. Applications to graph clustering are provided as an illustration. 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.
Item Type:  Article  

Related URLs: 
 
ORCID: 
 
Additional Information:  Received by the editors March 2, 2006; accepted for publication (in revised form) by R. Nabben September 11, 2007; published electronically April 23, 2008. This research was supported by NSF grant CCF0431257, NSF Career Award ACI0093404, and NSFITR award IIS0325116. A preliminary version of this work appeared at NIPS 2004, Vancouver, Canada.  
Funders: 
 
Subject Keywords:  matrix nearness problems, metric, distance matrix, metric nearness, all pairs shortest paths, triangle inequality  
Classification Code:  AMS: 05C12, 05C85, 54E35, 65Y20, 90C06, 90C08  
Record Number:  CaltechAUTHORS:20110513152152857  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20110513152152857  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  23672  
Collection:  CaltechAUTHORS  
Deposited By:  Kristin Buxton  
Deposited On:  13 May 2011 22:32  
Last Modified:  06 Mar 2015 23:10 
Repository Staff Only: item control page