Hyperbolic Distance Geometry Problems

2m ago
1 Views
0 Downloads
7.84 MB
64 Pages
Last View : 2m ago
Last Download : n/a
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 .

1 Hyperbolic space and its isometries 1 1.1 Möbius transformations 1 1.2 Hyperbolic geometry 6 1.2.1 The hyperbolic plane 8 1.2.2 Hyperbolic space 8 1.3 The circle or sphere at infinity 12 1.4 Gaussian curvature 16 1.5 Further properties of Möbius transformations 19 1.5.1 Commutativity 19 1.5.2 Isometric circles and planes 20 1.5.3 Trace .

metrical properties of the hyperbolic space are very differ-ent. It is known that hyperbolic space cannot be isomet-rically embedded into Euclidean space [18, 24], but there exist several well-studied models of hyperbolic geometry. In every model, a certain subset of Euclidean space is en-dowed with a hyperbolic metric; however, all these models

Unfortunately, each model of the Hyperbolic geometry depicts a warped version of the Hyperbolic space, just as a two-dimensional map represents the Earth in a distorted way. To describe the Hyperbolic space, all we need to know is the amount of distortion introduced . Hyperbolic space of curvature k is: d(x,y) arccosh s (1 Xn i 1 x2

2 Background on hyperbolic geometry Hyperbolic space is a non-Euclidean space with a negative constant sectional curvature and an underlying geometry that describes tree-like graphs with small distortions [46]. There exist four commonly-used models for hyperbolic spaces: Poincaré disk model, Lorentz model (hyperboloid

hyperbolic geometry is described. Then, an experiment with well established Euclidean colour metrics and colour difference data sets is conducted and the results are compared to the state-of-the-art colour metric CIEDE2000. 2. Transformation to hyperbolic geometry The Poincaré disk is one of the most commonly used models of the hyperbolic .

To display Ii hyperbolic spiral, we must first choose a (Euclidean) model of hyperbolic geometry, since as has been known for 100 years, there is no smooth distance-preserving embedding of hyperbolic geometry in Euclidean space. The Poincare circle model suits our needs best because (1) it lies entirely within a

course. Instead, we will develop hyperbolic geometry in a way that emphasises the similar-ities and (more interestingly!) the many differences with Euclidean geometry (that is, the 'real-world' geometry that we are all familiar with). §1.2 Euclidean geometry Euclidean geometry is the study of geometry in the Euclidean plane R2, or more .

One difficulty for defining the hyperbolic CVT is how to well de-fine the centroid of a given region in 2D hyperbolic space. In this paper, we extend the model centroid [Galperin 1993] to define the centroid of a Voronoi cell in 2D hyperbolic space. Another chal-lenge is how to effectively and efficiently compute the hyperbolic CVT.

In recent years, mathematicians have become interested in creating hyperbolic patterns using computers. Dunham outlines the creation of hyperbolic patterns in [12]. Chung, Chan, and Wang create escape time images with hyperbolic symmetry in [13]. We develop a method of creating iterated function systems with symmetries in the hyperbolic plane.

also apply to δ-hyperbolic spaces. In [3], Chepoi et al. present schemes for computing an additive approximation of the diameter, center, and radius of δ-hyperbolic spaces and graphs. They also show that several graph classes are δ-hyperbolic and present a linear-time algorithm for approx-imating trees of n-node δ-hyperbolic graphs with O .

hyperbolic lines/shape (H 2) in R . 5.3 Properties of Hyperbolic Geometry in H2 Back to the equilateral octagon we used in double torus parameterization, we could recon-struct the equilateral octagon in hyperbolic plane H2 that preserve the same length yet have a di erent sum of interior angles. 7

3.1. Hyperbolic Geometry & Poincaré Embeddings Hyperbolic space is the unique, complete, simply connected Riemannian manifold with constant negative sectional curva-ture. There exist multiple equivalent1 models for hyperbolic space and one can choose the model whichever is best suited for a given task.Nickel & Kiela(2017) based their approach

IN ARTIFICIAL INTELLIGENCE Stuart Russell and Peter Norvig, Editors FORSYTH & PONCE Computer Vision: A Modern Approach GRAHAM ANSI Common Lisp JURAFSKY & MARTIN Speech and Language Processing, 2nd ed. NEAPOLITAN Learning Bayesian Networks RUSSELL & NORVIG Artificial Intelligence: A Modern Approach, 3rd ed. Artificial Intelligence A Modern Approach Third Edition Stuart J. Russell and Peter .