论文标题
双曲距离矩阵
Hyperbolic Distance Matrices
论文作者
论文摘要
双曲线空间是使用分层结构进行挖掘和可视化数据的自然环境。为了根据比较或相似性信息计算双曲线嵌入，必须解决双曲线距离几何问题。在本文中，我们提出了一个统一的框架，以从嘈杂的度量和非金属数据的任意组合中计算双曲线嵌入。我们的算法基于半决赛编程和双曲距离矩阵的概念，在许多方面与其著名的欧几里得对应物平行。我们提出的一种中心成分是对双曲线格拉米亚高质体的半决赛表征 - 洛伦兹内部产品的基质。这种表征使我们能够在两个阶段中制定半芬矿放松，以有效地计算双曲线嵌入：首先，我们完成并将观察到的双曲线距离矩阵定义；其次，我们提出了一种光谱分解方法，以估算双曲线距离矩阵的嵌入点。我们通过数值实验来展示如何混合度量和非视频约束的灵活性使我们能够从任意数据中有效地计算嵌入。
Hyperbolic space is a natural setting for mining and visualizing data with hierarchical structure. In order to compute a hyperbolic embedding from comparison or similarity information, one has to solve a hyperbolic distance geometry problem. In this paper, we propose a unified framework to compute hyperbolic embeddings from an arbitrary mix of noisy metric and non-metric data. Our algorithms are based on semidefinite programming and the notion of a hyperbolic distance matrix, in many ways parallel to its famous Euclidean counterpart. A central ingredient we put forward is a semidefinite characterization of the hyperbolic Gramian -- a matrix of Lorentzian inner products. This characterization allows us to formulate a semidefinite relaxation to efficiently compute hyperbolic embeddings in two stages: first, we complete and denoise the observed hyperbolic distance matrix; second, we propose a spectral factorization method to estimate the embedded points from the hyperbolic distance matrix. We show through numerical experiments how the flexibility to mix metric and non-metric constraints allows us to efficiently compute embeddings from arbitrary data.
