Hyperbolic Distance Geometry Problems
A typical distance geometry problem (DGP) is concerned with finding the positions of a set of points in a d-dimensional Euclidean space from a set of pairwise distance-related measurements. This generic definition finds relevance to a wide variety of real-world applications including molecular conformation, robotics, and sensor network localization. A priori knowledge about the geometry of underlying data points dictates the choice of the embedding space. In this talk, I will focus on DGPs in which distance measurements are derived from tree (data) graphs. This prompts working in hyperbolic rather than Euclidean spaces as the former are much more appropriate for tree-structured data. I will cover basic notions of hyperbolic geometry such as generalized straight lines, tangent spaces, and distances. I will then formally introduce a hyperbolic distance geometry problem and show how to cast it as a rank-constrained semidefinite program. This yields a semidefinite relaxation for mixed metric and non-metric hyperbolic DGPs. Then, I will briefly talk about how to solve the hyperbolic Procrustes problems, in which we aim to find the alignment between two hyperbolic point sets. I will end my talk by posing a fundamental question: How to learn the geometry of a point set from distance comparisons?