Hyperbolic Distance Geometry Problems

1y ago
14 Views
3 Downloads
7.84 MB
64 Pages
Last View : 2m ago
Last Download : 2m ago
Upload by : Annika Witter
Transcription

Hyperbolic Distance Geometry ProblemsPuoya Tabaghia joint work with Ivan DokmanićUniversity of Illinois at Urbana-ChampaignCoordinated Science LabMini-symposium on Sensor Network Localization and DynamicalDistance GeometryThe Fields Institute, CanadaMay 20, 2021Puoya TabaghiHyperbolic Distance Geometry Problems1 / 31

introductiondistance geometry problems (DGPs)to find a realization for a set of entities given a set of distance-relatedmeasurementsPuoya TabaghiHyperbolic Distance Geometry Problems2 / 31

introductiondistance geometry problems (DGPs)to find a realization for a set of entities given a set of distance-relatedmeasurementsPuoya TabaghiHyperbolic Distance Geometry Problems2 / 31

introductiondistance geometry problems (DGPs)to find a realization for a set of entities given a set of distance-relatedmeasurements when dissimilarities are Euclidean distances: metric multidimensional scaling, PCA, metric DGP manifold learning (preserve local distances)Puoya TabaghiHyperbolic Distance Geometry Problems2 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]Puoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]Puoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]3 robotics [Cornejo ’15]Puoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]3 robotics [Cornejo ’15] but there exists other types of data associated with graphs,specifically treesPuoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]3 robotics [Cornejo ’15] but there exists other types of data associated with graphs,specifically treesPuoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]3 robotics [Cornejo ’15] but there exists other types of data associated with graphs,specifically trees taxonomies in biology, concept hierarchies in computationallinguistics, .Puoya TabaghiHyperbolic Distance Geometry Problems3 / 31

why hyperbolic spaces? hyperbolic spaces can embed hierarchical structures witharbitrarily low distortion [Sarkar, ’11]Puoya TabaghiHyperbolic Distance Geometry Problems4 / 31

why hyperbolic spaces? hyperbolic spaces can embed hierarchical structures witharbitrarily low distortion [Sarkar, ’11] the number of leaves of a tree can grow exponentially(constant branching factor) Euclidean space: vol BEd (r ) O(r d ) 2 hyperbolic space: vol BHd (r ) O(r d e (d 1)r )1Puoya TabaghiHyperbolic Distance Geometry Problems4 / 31

why hyperbolic spaces? hyperbolic spaces can embed hierarchical structures witharbitrarily low distortion [Sarkar, ’11] the number of leaves of a tree can grow exponentially(constant branching factor) Euclidean space: vol BEd (r ) O(r d ) 2 hyperbolic space: vol BHd (r ) O(r d e (d 1)r )1Figure: a weighted tree embedded in (a) hyperbolic space and (b) Euclidean spacePuoya TabaghiHyperbolic Distance Geometry Problems4 / 31

examples of hierarchical dataPuoya TabaghiHyperbolic Distance Geometry Problems5 / 31

examples of hierarchical dataPuoya TabaghiHyperbolic Distance Geometry Problems5 / 31

outline1. hyperbolic spaces2. hyperbolic distance geometryproblemsPuoya Tabaghi3. hyperbolic Procrustes analysis4. geometry of similaritiesHyperbolic Distance Geometry Problems6 / 31

models of hyperbolic space half-space (H), Poincaré (I), jemisphere (J), Klein (K), and’Loid (L) models there is a distance-preserving bijection between each pairPuoya TabaghiHyperbolic Distance Geometry Problems7 / 31

geodesics in hyperbolic spaces the shortest path between x, y Ld belongs tospan {x, y } Ld the stereographic projection gives the geodesics in PoincarémodelPuoya TabaghiHyperbolic Distance Geometry Problems8 / 31

Lorentzian spaceDefinitionLet x and y be vectors in Rd 1 with d 1. The Lorentzian innerproduct of x and y is defined as[x, y ] x Hy ,where H Puoya Tabaghi 1 0 0I R(d 1) (d 1) .Hyperbolic Distance Geometry Problems9 / 31

Lorentzian spaceDefinitionLet x and y be vectors in Rd 1 with d 1. The Lorentzian innerproduct of x and y is defined as[x, y ] x Hy ,where H 1 0 0I R(d 1) (d 1) . similarly, we can define H-adjoint, H-unitary operators, and .Puoya TabaghiHyperbolic Distance Geometry Problems9 / 31

’Loid model of hyperbolic spaceDefinitionThe ’Loid model of d-dimensional hyperbolic space is a Riemannianmanifold Ld (Ld , (gx )x ), wherenoLd x Rd 1 : [x, x] 1, x1 0and the Riemannian metric gx (u, v ) [u, v ] where u, v Tx Ld .Puoya TabaghiHyperbolic Distance Geometry Problems10 / 31

’Loid model of hyperbolic spaceDefinitionThe ’Loid model of d-dimensional hyperbolic space is a Riemannianmanifold Ld (Ld , (gx )x ), wherenoLd x Rd 1 : [x, x] 1, x1 0and the Riemannian metric gx (u, v ) [u, v ] where u, v Tx Ld . the Lorentzian inner product determines the distance betweenx, y Ld , asd(x, y ) acosh( [x, y ])Puoya TabaghiHyperbolic Distance Geometry Problems10 / 31

tangent space the tangent space at point x Ld is given bynoTx Ld v Rd 1 : [x, v ] 0Puoya TabaghiHyperbolic Distance Geometry Problems11 / 31

tangent space the tangent space at point x Ld is given bynoTx Ld v Rd 1 : [x, v ] 0 the exponential map expx : Tx Ld Ld can be used forgradient-based optimizationsexpx (v ) cosh kv k x sinh kv kPuoya Tabaghivkv kHyperbolic Distance Geometry Problems11 / 31

tangent space the tangent space at point x Ld is given bynoTx Ld v Rd 1 : [x, v ] 0 the exponential map expx : Tx Ld Ld can be used forgradient-based optimizationsexpx (v ) cosh kv k x sinh kv kPuoya Tabaghivkv kHyperbolic Distance Geometry Problems11 / 31

hyperbolic distance geometry problems hyperbolic DGPs 1 : to find an embedding for a set of entitiesin a hyperbolic space that realizes a given set of metric and/orsimilarity measurementsFigure: (a): encode the measurements in hyperbolic distance matrix(HDM), (b): complete the HDM, (c): estimate the point set positions1“Hyperbolic Distance Matrices”, KDD ’20Puoya TabaghiHyperbolic Distance Geometry Problems12 / 31

hyperbolic distance matrix & Gramian a hyperbolic distance matrix (HDM) D D(X ) encodesinter-point distances for a point set X Ld Nd(xi , xj ) acosh( gij ) where gij [xi , xj ] xi HxjPuoya TabaghiHyperbolic Distance Geometry Problems13 / 31

hyperbolic distance matrix & Gramian a hyperbolic distance matrix (HDM) D D(X ) encodesinter-point distances for a point set X Ld Nd(xi , xj ) acosh( gij ) where gij [xi , xj ] xi Hxj HDM is a non-linear function of the hyperbolic Gramian, i.e.,D acosh[ G ], where G X HXwhere acosh[·] is an elementwise acosh(·) operatorPuoya TabaghiHyperbolic Distance Geometry Problems13 / 31

semidefinite characterization of hyperbolic GramianspropositionLet G be the hyperbolic Gramian for a set of points x1 , · · · , xN Ld .Puoya TabaghiHyperbolic Distance Geometry Problems14 / 31

semidefinite characterization of hyperbolic GramianspropositionLet G be the hyperbolic Gramian for a set of points x1 , · · · , xN Ld .Then,G G G wherePuoya TabaghiG , G 0,rank G d, rank G 1, xn Rd,1ei Gei 1, i [N], xn Ld Ldei Gej 1, i, j [N]. xn LdHyperbolic Distance Geometry Problems14 / 31

semidefinite characterization of hyperbolic GramianspropositionLet G be the hyperbolic Gramian for a set of points x1 , · · · , xN Ld .Then,G G G whereG , G 0,rank G d, rank G 1, xn Rd,1ei Gei 1, i [N], xn Ld Ldei Gej 1, i, j [N]. xn LdConversely, any matrix G RN N that satisfies the above conditions is ahyperbolic Gramian for a set of N points in Ld .Puoya TabaghiHyperbolic Distance Geometry Problems14 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij )Puoya TabaghiHyperbolic Distance Geometry Problems15 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij ) equivalently: cosh(deij ) gijPuoya TabaghiHyperbolic Distance Geometry Problems15 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij ) equivalently: cosh(deij ) gij Let W be a measurement mask. The quadratic constrainte GW cosh[D] 2F enforces the accuracy of the estimated hyperbolic Gramian.Puoya TabaghiHyperbolic Distance Geometry Problems15 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij ) equivalently: cosh(deij ) gij Let W be a measurement mask. The quadratic constrainte GW cosh[D] 2F enforces the accuracy of the estimated hyperbolic Gramian. we can write non-metric measurements,d(xi1 , xi2 ) d(xi3 , xi4 ) acosh( gi1 i2 ) acosh( gi3 i4 )as a linear constraint in the form ofLi (G ) ei 1 Gei2 ei 3 Gei4 0Puoya TabaghiHyperbolic Distance Geometry Problems15 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij ) equivalently: cosh(deij ) gij Let W be a measurement mask. The quadratic constrainte GW cosh[D] 2F enforces the accuracy of the estimated hyperbolic Gramian. we can write non-metric measurements,d(xi1 , xi2 ) d(xi3 , xi4 ) acosh( gi1 i2 ) acosh( gi3 i4 )as a linear constraint in the form ofLi (G ) ei 1 Gei2 ei 3 Gei4 0“linear and quadratic data-fidelity constraints”Puoya TabaghiHyperbolic Distance Geometry Problems15 / 31

HDGP: semidefinite relaxationsemidefinite relaxation (SDR)for appropriate 1 , 2 0, solve for G :minimizeTr G Tr G trace is a surrogate for rankw.r.tG , G 0subject toG G G ,ei Gei 1, i [N]ei Gej 1,e GW cosh[D]Lk (G ) 2 ,Puoya Tabaghi i, j [N] 2F 1 , k K .Hyperbolic Distance Geometry Problems16 / 31

from SDR to the embedding H-Gramian estimated by the semidefinite relaxation does notnecessarily have the correct rank projection w/ Riemanniangradient descentPuoya TabaghiHyperbolic Distance Geometry Problems17 / 31

from SDR to the embedding H-Gramian estimated by the semidefinite relaxation does notnecessarily have the correct rank projection w/ Riemanniangradient descentproposition NLet G be a hyperbolic Gramian for X Ld , with eigenvalue decomposition G UΛU , and eigenvalues λ0 0 λ1 . . . λd .Then, there exists an H-unitary matrix R such that X R Λ 1/2 U.Puoya TabaghiHyperbolic Distance Geometry Problems17 / 31

embedding with missing measurements random hyperbolic point sets with sparse metric andnon-metric measurementsFigure: left: the probability of an accurate estimation for metric samplingdensity S, right: the empirical error for ordinal sampling density SPuoya TabaghiHyperbolic Distance Geometry Problems18 / 31

weighted tree embedding random weighted trees of size NFigure: Tree embedding in hyperbolic (red) and Euclidean (green) space.Discrete distribution of optimal embedding dimension.Puoya TabaghiHyperbolic Distance Geometry Problems19 / 31

hyperbolic Procrustes analysis we ask: how can we align two embedded trees that have a fewnodes in common?2“On Procrustes Analysis in Hyperbolic Space”, Signal Processing Letters,2021Puoya TabaghiHyperbolic Distance Geometry Problems20 / 31

hyperbolic Procrustes analysis we ask: how can we align two embedded trees that have a fewnodes in common? Procrustes analysis 2 : to find an isometry between two sets ofhyperbolic points to best superimpose them onto each otherFigure: tree alignment in Poincaré disk. (a) and (b) we center each pointset, and (c) estimate the unknown rotation map2“On Procrustes Analysis in Hyperbolic Space”, Signal Processing Letters,2021Puoya TabaghiHyperbolic Distance Geometry Problems20 / 31

hyperbolic isometries any hyperbolic isometry is a composition of two elementarymaps: translation and rotation (and reflection)Puoya TabaghiHyperbolic Distance Geometry Problems21 / 31

hyperbolic isometries any hyperbolic isometry is a composition of two elementarymaps: translation and rotation (and reflection)elementary isometriesThe function T : Ld Ld is an isometry if and only if it can be writtenas T (x) RU Rb x, where" q# 2 1 0 1 kbkbRU , Rb 10 Ub(I bb ) 2for a unitary matrix U O(d) and a vector b Rd . More over, Rb 1 R b and RU 1 RU .Puoya TabaghiHyperbolic Distance Geometry Problems21 / 31

hyperbolic isometries, visualizedFigure: (a) hyperbolic rotation, (b) hyperbolic translationPuoya TabaghiHyperbolic Distance Geometry Problems22 / 31

hyperbolic Procrustes analysis hyperbolic center mass of x1 , . . . , xN Ld ismx arg maxz RdPuoya Tabaghi1 X[xn , Q(z)] a notion of addition in LdNn [N]Hyperbolic Distance Geometry Problems23 / 31

hyperbolic Procrustes analysis hyperbolic center mass of x1 , . . . , xN Ld ismx arg maxz Rd1 X[xn , Q(z)] a notion of addition in LdNn [N]proposition: decoupling hyperbolic rotation and translationLet x1 , . . . , xN and x10 , . . . xN0 in Ld such that xn Rb RU xn0 , n [N].Then, R mx xn RV R mx 0 xn0 where RV is a hyperbolic rotation matrix.Puoya TabaghiHyperbolic Distance Geometry Problems23 / 31

hyperbolic Procrustes: rotation & reflection we estimate the unknown hyperbolic rotation by solvingUb arg maxXV O(d) n [N][R mx xn , RV R mx 0 xn0 ](1)propositionThe optimal unitary matrix that solves (1) is Ub Ul Ur ,where Ul ΣUr is the singular value decomposition ofP(R mx X )P(R mx 0 X 0 ) .Puoya TabaghiHyperbolic Distance Geometry Problems24 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare!Puoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domainPuoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domain1 correlations & co-occurrencesPuoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domain1 correlations & co-occurrences2 perceptual and crowd-sourced dataPuoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domain1 correlations & co-occurrences2 perceptual and crowd-sourced data3 biological dataPuoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domain1 correlations & co-occurrences2 perceptual and crowd-sourced data3 biological data can we reveal the geometry from similarity measurements only(no metric information)?Puoya TabaghiHyperbolic Distance Geometry Problems25 / 31

similarities orders similarity measurements: i, j [N] : yij φ d(xi , xj ) where φ(·) is an unknown monotonically decreasing function this model transforms similarities to ordinal measurements i, j, k, l [N] : yi,j yk,l d(xi , xj ) d(xk , xl )Puoya TabaghiHyperbolic Distance Geometry Problems26 / 31

ordinal spread consider similarity measurements {yi,j }i,j [6] with the followingsorted distance list,d(x1 , x2 ) d(x2 , x3 ) d(x1 , x3 ) d(x4 , x5 ) · · · d(x5 , x6 ) our proposal: the ranking of the first appearance of the k-thpoint in the sorted distance list — or the the ordinal spread αkα (α1 , α2 , α3 , α4 , α5 , α6 ) (1, 1, 2, 4, 4, 11)Puoya TabaghiHyperbolic Distance Geometry Problems27 / 31

random ordinal spread variable on similarity graphs we can compute the empirical PMF of αN for a large similaritygraph ( V N)Puoya TabaghiHyperbolic Distance Geometry Problems28 / 31

hyperbolicity of weighted trees our proposed hypothesis test:1 compute the empirical PαN from a randomly generatedweighted tree2 find the best match from random point sets in each space formH2 , E2 and S2Puoya TabaghiHyperbolic Distance Geometry Problems29 / 31

conclusion metric/non-metric trees can be faithfully embedded in ahyperbolic spacePuoya TabaghiHyperbolic Distance Geometry Problems30 / 31

conclusion metric/non-metric trees can be faithfully embedded in ahyperbolic space a semidefinite relaxation can solve hyperbolic distancegeometry problemsPuoya TabaghiHyperbolic Distance Geometry Problems30 / 31

conclusion metric/non-metric trees can be faithfully embedded in ahyperbolic space a semidefinite relaxation can solve hyperbolic distancegeometry problems hyperbolic Procrustes analysis is (almost) identical to itsEuclidean versionPuoya TabaghiHyperbolic Distance Geometry Problems30 / 31

conclusion metric/non-metric trees can be faithfully embedded in ahyperbolic space a semidefinite relaxation can solve hyperbolic distancegeometry problems hyperbolic Procrustes analysis is (almost) identical to itsEuclidean version even non-metric measurements can encode geometricalinformationPuoya TabaghiHyperbolic Distance Geometry Problems30 / 31

Thank you!

Puoya Tabaghi Hyperbolic Distance Geometry Problems 4 / 31. examplesofhierarchicaldata Puoya Tabaghi Hyperbolic Distance Geometry Problems 5 / 31. examplesofhierarchicaldata Puoya Tabaghi Hyperbolic Distance Geometry Problems 5 / 31. outline 1. hyperbolicspaces 2. hyperbolicdistancegeometry

Related Documents:

equal to ˇ. In hyperbolic geometry, 0 ˇ. In spherical geometry, ˇ . Figure 1. L to R, Triangles in Euclidean, Hyperbolic, and Spherical Geometries 1.1. The Hyperbolic Plane H. The majority of 3-manifolds admit a hyperbolic struc-ture [Thurston], so we shall focus primarily on the hyperbolic geometry, starting with the hyperbolic plane, H.

Volume in hyperbolic geometry H n - the hyperbolic n-space (e.g. the upper half space with the hyperbolic metric ds2 dw2 y2). Isom(H n) - the group of isometries of H n. G Isom(H n), a discrete subgroup )M H n G is a hyperbolic n-orbifold. M is a manifold ()G is torsion free. We will discuss finite volume hyperbolic n-manifolds and .

shortest paths connecting two point in the hyperbolic plane. After a brief introduction to the Poincar e disk model, we will talk about geodesic triangleand we will give a classi cation of the hyperbolic isome-tries. In the end, we will explain why the hyperbolic geometry is an example of a non-Euclidean geometry.

triangles, circles, and quadrilaterals in hyperbolic geometry and how familiar formulas in Euclidean geometry correspond to analogous formulas in hyperbolic geometry. In fact, besides hyperbolic geometry, there is a second non-Euclidean geometry that can be characterized by the behavi

geodesic distance is the arc-length of the unique hyperbolic line joining x and y and equals the hyperbolic distance d(x;y). 1.3 The Conformal Model of Hyperbolic Geometry Distorting the projective model leads to a new model of hyperbolic geometry with some other special metric properties: Let H2 be the interior of the unit circle and de ne .

Geometry of conformal metrics The hyperbolic metric on the disc hyperbolic distance Definition The hyperbolic distance between two points z and w is d(z;w) inf Z jdzj 1 j zj2: Definition A geodesic segment between two points is a curve which attains the minimum distance. Warning: This is not the usual definition, but in the case of the

The angle between hyperbolic rays is that between their (Euclidean) tangent lines: angles are congruent if they have the same measure. q Lemma 5.10. The hyperbolic distancea of a point P from the origin is d(O, P) cosh 1 1 jPj2 1 jPj2 ln 1 jPj 1 jPj aIt should seem reasonable for hyperbolic functions to play some role in hyperbolic .

The Pearson Edexcel Level 3 Advanced GCE in Business is designed for use in schools and colleges. It is part of a suite of GCE qualifications offered by Pearson. These sample assessment materials have been developed to support this qualification and will be used as the benchmark to develop the assessment students will take. P v 3 1 2014 2014 2. P v 3 1 2014 2014 3 General marking guidance .