Exact Computation Of A Manifold Metric, Via Lipschitz Embeddings And Shortest Paths On A Graph

Abstract

Data-sensitive metrics adapt distances locally based the density of data points with the goal of aligning distances and some notion of similarity. In this paper, we give the first exact algorithm for computing a data-sensitive metric called the nearest neighbor metric. In fact, we prove the surprising result that a previously published \(3\)-approximation is an exact algorithm. The nearest neighbor metric can be viewed as a special case of a density-based distance used in machine learning, or it can be seen as an example of a manifold metric. Previous computational research on such metrics despaired of computing exact distances on account of the apparent difficulty of minimizing over all continuous paths between a pair of points. We leverage the exact computation of the nearest neighbor metric to compute sparse spanners and persistent homology. We also explore the behavior of the metric built from point sets drawn from an underlying distribution and consider the more general case of

Stats

• citations4
• S2 citations—
• github stars0
• HF likes0
• heat score5.24
• arxiv keychu2017exact

Related papers

• Computationally Efficient Learning Of Statistical Manifolds (2021)0.00
• Metric Learning On Manifolds (2019)0.00
• Accurate And Fast Retrieval For Complex Non-metric Data Via Neighborhood Graphs (2019)0.00
• Local Distance Metric Learning For Nearest Neighbor Algorithm (2018)0.00
• Approximate Near Neighbors For General Symmetric Norms (2016)8.35
• Robust Mahalanobis Metric Learning Via Geometric Approximation Algorithms (2019)0.00
• Sublinear Data Structures For Nearest Neighbor In Ultra High Dimensions (2025)0.00
• Navigable Graphs For High-dimensional Nearest Neighbor Search: Constructions And Limits (2024)4.52