Dan P. Guralnik

Dan P. Guralnik
Are you Dan P. Guralnik?

Claim your profile, edit publications, add additional information:

Contact Details

Dan P. Guralnik

Pubs By Year

Pub Categories

Mathematics - Group Theory (4)
Statistics - Machine Learning (4)
Computer Science - Learning (4)
Mathematics - Metric Geometry (3)
Computer Science - Robotics (2)
Computer Science - Artificial Intelligence (2)
Mathematics - Dynamical Systems (1)
Quantitative Biology - Neurons and Cognition (1)
Computer Science - Data Structures and Algorithms (1)
Mathematics - Differential Geometry (1)
Computer Science - Computational Engineering; Finance; and Science (1)
Quantitative Biology - Populations and Evolution (1)
Computer Science - Computational Geometry (1)
Mathematics - Geometric Topology (1)

Publications Authored By Dan P. Guralnik

This work draws its inspiration from three important sources of research on dissimilarity-based clustering and intertwines those three threads into a consistent principled functorial theory of clustering. Those three are the overlapping clustering of Jardine and Sibson, the functorial approach of Carlsson and Memoli to partition-based clustering, and the Isbell/Dress school's study of injective envelopes. Carlsson and Memoli introduce the idea of viewing clustering methods as functors from a category of metric spaces to a category of clusters, with functoriality subsuming many desirable properties. Read More

We examine overlapping clustering schemes with functorial constraints, in the spirit of Carlsson--Memoli. This avoids issues arising from the chaining required by partition-based methods. Our principal result shows that any clustering functor is naturally constrained to refine single-linkage clusters and be refined by maximal-linkage clusters. Read More

Distance-based hierarchical clustering (HC) methods are widely used in unsupervised data analysis but few authors take account of uncertainty in the distance data. We incorporate a statistical model of the uncertainty through corruption or noise in the pairwise distances and investigate the problem of estimating the HC as unknown parameters from measurements. Specifically, we focus on single linkage hierarchical clustering (SLHC) and study its geometry. Read More

We derive a statistical model for estimation of a dendrogram from single linkage hierarchical clustering (SLHC) that takes account of uncertainty through noise or corruption in the measurements of separation of data. Our focus is on just the estimation of the hierarchy of partitions afforded by the dendrogram, rather than the heights in the latter. The concept of estimating this "dendrogram structure'' is introduced, and an approximate maximum likelihood estimator (MLE) for the dendrogram structure is described. Read More

We introduce the use of hierarchical clustering for relaxed, deterministic coordination and control of multiple robots. Traditionally an unsupervised learning method, hierarchical clustering offers a formalism for identifying and representing spatially cohesive and segregated robot groups at different resolutions by relating the continuous space of configurations to the combinatorial space of trees. We formalize and exploit this relation, developing computationally effective reactive algorithms for navigating through the combinatorial space in concert with geometric realizations for a particular choice of hierarchical clustering method. Read More

We propose a self-organizing memory architecture for perceptual experience, capable of supporting autonomous learning and goal-directed problem solving in the absence of any prior information about the agent's environment. The architecture is simple enough to ensure (1) a quadratic bound (in the number of available sensors) on space requirements, and (2) a quadratic bound on the time-complexity of the update-execute cycle. At the same time, it is sufficiently complex to provide the agent with an internal representation which is (3) minimal among all representations of its class which account for every sensory equivalence class subject to the agent's belief state; (4) capable, in principle, of recovering the homotopy type of the system's state space; (5) learnable with arbitrary precision through a random application of the available actions. Read More

In his pioneering work on injective metric spaces Isbell attempted a characterization of cellular complexes admitting the structure of an injective metric space, following his discovery that finite metric spaces have injective envelopes naturally admitting a polyhedral structure. Considerable advances in the understanding, classification and applications of injective envelopes have been made by Dress, Huber, Sturmfels and collaborators (producing, among other results, many specific examples of injective polyhedra), and most recently by Lang, yet a combination theory explaining how to glue injective polyhedra together to produce large families of injective spaces is still unavailable. In this paper we apply the duality theory of cubings -- simply connected non-positively curved cubical complexes -- to provide a more principled and accessible proof of a result of Mai and Tang on the injective metrizability of collapsible simplicial complexes. Read More

In this paper we introduce and study three new measures for efficient discriminative comparison of phylogenetic trees. The NNI navigation dissimilarity $d_{nav}$ counts the steps along a "combing" of the Nearest Neighbor Interchange (NNI) graph of binary hierarchies, providing an efficient approximation to the (NP-hard) NNI distance in terms of "edit length". At the same time, a closed form formula for $d_{nav}$ presents it as a weighted count of pairwise incompatibilities between clusters, lending it the character of an edge dissimilarity measure as well. Read More

We introduce the class of perturbed right-angled Artin groups. These are constructed by gluing Bieri double groups into standard right-angled Artin groups. As a first application of this construction we obtain families of CAT(0) groups containing finitely presented subgroups which are not of type $\mathrm{FP}_3$, and have exponential, or polynomial Dehn functions of prescribed degree. Read More

We introduce new techniques for studying boundary dynamics of CAT(0) groups. For a group $G$ acting geometrically on a CAT(0) space $X$ we show there is a flat $F\subset X$ of maximal dimension whose boundary sphere intersects every minimal $G$-invariant subset of $\partial_\infty X$. As a result we derive a necessary and sufficient dynamical condition for $G$ to be virtually-Abelian, as well as a new approach to Ballmann's rank rigidity conjecture. Read More

We consider a living organism as an observer of the evolution of its environment recording sensory information about the state space X of the environment in real time. Sensory information is sampled and then processed on two levels. On the biological level, the organism serves as an evaluation mechanism of the subjective relevance of the incoming data to the observer: the observer assigns excitation values to events in X it could recognize using its sensory equipment. Read More

In this work we introduce a new combinatorial notion of boundary $\Re C$ of an $\omega$-dimensional cubing $C$. $\Re C$ is defined to be the set of almost-equality classes of ultrafilters on the standard system of halfspaces of $C$, endowed with an order relation reflecting the interaction between the Tychonoff closures of the classes. When $C$ arises as the dual of a cubulation -- or discrete system of halfspaces -- $\HH$ of a CAT(0) space $X$ (for example, the Niblo-Reeves cubulation of the Davis-Moussong complex of a finite rank Coxeter group), we show how $\HH$ induces a function $\rho:\bd X\to\Re C$. Read More

Let X be a proper CAT(0) space. A halfspace system (or cubulation) of X is a set H of open halfspaces closed under closure-complementation and such that every point in X has a neighbourhood intersecting only finitely many walls of H. Given a cubulation H, one uses the Sageev-Roller construction to form a cubing C(H). Read More