Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph
Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph
复制标题
DOI：
10.1137/1.9781611975994.25
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
T. Chu;G. Miller;Don Sheehy
中科院分区：
文献类型：
--
作者：
T. Chu;G. Miller;Don Sheehy
数据敏感指标根据数据点的密度局部调整距离，其目标是对齐距离和一些相似性概念。在本文中，我们给出了第一个用于计算数据敏感度量（称为最近邻度量）的精确算法。事实上，我们证明了令人惊讶的结果，即之前发布的 3 美元近似值是一个精确算法。最近邻度量可以被视为机器学习中使用的基于密度的距离的特例，也可以被视为流形度量的示例。先前对此类度量的计算研究对计算精确距离感到绝望，因为最小化一对点之间的所有连续路径显然很困难。我们利用最近邻度量的精确计算来计算稀疏扳手和持久同源性。我们还探索了从基础分布中提取的点集构建的度量的行为，并考虑了更一般的输入情况，即路径连接的紧凑集的有限集合。主要成果连接了黎曼度量的共形变、勋伯格正定函数理论、勋伯格和冯·诺依曼的旋量函数理论等多个经典理论。我们基于螺旋函数和 Lipschitz 扩展的组合开发了新颖的证明技术，这些技术可能具有独立的意义。
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 inputs that are finite collections of path-connected compact sets. The main results connect several classical theories such as the conformal change of Riemannian metrics, the theory of positive definite functions of Schoenberg, and screw function theory of Schoenberg and Von Neumann. We develop novel proof techniques based on the combination of screw functions and Lipschitz extensions that may be of independent interest.