IEEE Xplore Abstract - Geographic Routing Using Hyperbolic Space

march 2014 by cshalizi

"We propose a scalable and reliable point-to-point routing algorithm for ad hoc wireless networks and sensor-nets. Our algorithm assigns to each node of the network a virtual coordinate in the hyperbolic plane, and performs greedy geographic routing with respect to these virtual coordinates. Unlike other proposed greedy routing algorithms based on virtual coordinates, our embedding guarantees that the greedy algorithm is always successful in finding a route to the destination, if such a route exists. We describe a distributed algorithm for computing each node's virtual coordinates in the hyperbolic plane, and for greedily routing packets to a destination point in the hyperbolic plane. (This destination may be the address of another node of the network, or it may be an address associated to a piece of content in a Distributed Hash Table. In the latter case we prove that the greedy routing strategy makes a consistent choice of the node responsible for the address, irrespective of the source address of the request.) We evaluate the resulting algorithm in terms of both path stretch and node congestion."

multidimensional_scaling
graph_embedding
hyperbolic_geometry
re:network_differences
via:dena
networks
in_NB
re:hyperbolic_networks
march 2014 by cshalizi

Finding the Homology of Submanifolds with High Confidence from Random Samples

february 2013 by cshalizi

"Recently there has been a lot of interest in geometrically motivated approaches to data analysis in high-dimensional spaces. We consider the case where data is drawn from sampling a probability distribution that has support on or near a submanifold of Euclidean space. We show how to “learn” the homology of the submanifold with high confidence. We discuss an algorithm to do this and provide learning-theoretic complexity bounds. Our bounds are obtained in terms of a condition number that limits the curvature and nearness to self-intersection of the submanifold. We are also able to treat the situation where the data is “noisy” and lies near rather than on the submanifold in question."

in_NB
manifold_learning
statistics
topology
niyogi.partha
smale.stephen
via:dena
february 2013 by cshalizi

[1010.4202] M"{o}bius deconvolution on the hyperbolic plane with application to impedance density estimation

february 2013 by cshalizi

"In this paper we consider a novel statistical inverse problem on the Poincar'{e}, or Lobachevsky, upper (complex) half plane. Here the Riemannian structure is hyperbolic and a transitive group action comes from the space of $2times2$ real matrices of determinant one via M"{o}bius transformations. Our approach is based on a deconvolution technique which relies on the Helgason--Fourier calculus adapted to this hyperbolic space. This gives a minimax nonparametric density estimator of a hyperbolic density that is corrupted by a random M"{o}bius transform. A motivation for this work comes from the reconstruction of impedances of capacitors where the above scenario on the Poincar'{e} plane exactly describes the physical system that is of statistical interest."

have_read
density_estimation
deconvolution
statistics
hyperbolic_geometry
re:smoothing_adjacency_matrices
fourier_analysis
via:dena
in_NB
re:hyperbolic_networks
re:network_differences
february 2013 by cshalizi

**related tags**

Copy this bookmark: