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.
