cshalizi + via:dena   3

IEEE Xplore Abstract - Geographic Routing Using Hyperbolic Space
"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
"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
"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

Copy this bookmark: