Research
My research interests are in computational topology and geometry, combinatorial topology, and applied topology (in particular to data analysis and to sensor networks).
I am a member of the Pattern Analysis Lab.
Here is my PhD thesis, a related research highlight, and an outdated research statement.
Papers on VietorisRips and Čech complexes


Random cyclic dynamical systems.
With Michał Adamaszek and Francis Motta.
To appear in Advances in Applied Mathematics.
[arXiv:1511.07832,
Abstract]

For X a finite subset of the circle and for 0 < r ≤ 1 fixed, consider the function f_{r} : X → X which maps each point to the clockwise furthest element of X within angular distance less than 2πr. We study the discrete dynamical system on X generated by f_{r} , and especially its expected behavior when X is a large random set. We show that, as X → ∞, the expected fraction of periodic points of f_{r} tends to 0 if r is irrational and to 1/q if r = p/q is rational with p and q coprime. These results are obtained via more refined statistics of f_{r} which we compute explicitly in terms of (generalized) Catalan numbers. The motivation for studying f_{r} comes from VietorisRips complexes, a geometric construction used in computational topology. Our results determine how much one can expect to simplify the VietorisRips complex of a random sample of the circle by removing dominated vertices.
Given a metric space X and a distance threshold r > 0, the VietorisRips simplicial complex has as its simplices the finite subsets of X of diameter less than r. A theorem of JeanClaude Hausmann states that if X is a Riemannian manifold and r is sufficiently small, then the VietorisRips complex is homotopy equivalent to the original manifold. Little is known about the behavior of VietorisRips complexes for larger values of r, even though these complexes arise naturally in applications using persistent homology. We show that as r increases, the VietorisRips complex of the circle obtains the homotopy types of the circle, the 3sphere, the 5sphere, the 7sphere, ..., until finally it is contractible. As our main tool we introduce a directed graph invariant, the winding fraction, which in some sense is dual to the circular chromatic number. Using the winding fraction we classify the homotopy types of the VietorisRips complex of an arbitrary (possibly infinite) subset of the circle, and we study the expected homotopy type of the VietorisRips complex of a uniformly random sample from the circle. Moreover, we show that as the distance parameter increases, the ambient Čech complex of the circle also obtains the homotopy types of the circle, the 3sphere, the 5sphere, the 7sphere, ..., until finally it is contractible.


Nerve complexes of circular arcs.
With Michał Adamaszek, Florian Frick, Chris Peterson, and Corrine PreviteJohnson.
To appear in Discrete & Computational Geometry.
[SpringerLink,
arXiv:1410.4336,
Abstract]

We show that the nerve complex of n arcs in the circle is homotopy equivalent to either a point, an odddimensional sphere, or a wedge sum of spheres of the same even dimension. Moreover this homotopy type can be computed in time O(n log n). For the particular case of the nerve complex of evenlyspaced arcs of the same length, we determine the dihedral group action on homology, and we relate the complex to a cyclic polytope with n vertices. We give three applications of our knowledge of the homotopy types of nerve complexes of circular arcs. First, we use the connection to cyclic polytopes to give a novel topological proof of a known upper bound on the distance between successive roots of a homogeneous trigonometric polynomial. Second, we show that the Lovász bound on the chromatic number of a circular complete graph is either sharp or off by one. Third, we show that the VietorisRips simplicial complex of $n$ points in the circle is homotopy equivalent to either a point, an odddimensional sphere, or a wedge sum of spheres of the same even dimension, and furthermore this homotopy type can be computed in time O(n log n).
Papers on sensor networks
Suppose that ballshaped sensors wander in a bounded domain. A sensor doesn't know its location but does know when it overlaps a nearby sensor. We say that an evasion path exists in this sensor network if a moving intruder can avoid detection. In "Coordinatefree coverage in sensor networks with controlled boundaries via homology", Vin de Silva and Robert Ghrist give a necessary condition, depending only on the timevarying connectivity data of the sensors, for an evasion path to exist. Using zigzag persistent homology, we provide an equivalent condition that moreover can be computed in a streaming fashion. However, no method with timevarying connectivity data as input can give necessary and sufficient conditions for the existence of an evasion path. Indeed, we show that the existence of an evasion path depends not only on the fibrewise homotopy type of the region covered by sensors but also on its embedding in spacetime. For planar sensors that also measure weak rotation and distance information, we provide necessary and sufficient conditions for the existence of an evasion path.
Papers on data analysis


Persistence images: A stable vector representation of persistent homology.
With Sofya Chepushtanova, Tegan Emerson, Eric Hanson, Michael Kirby, Francis Motta, Rachel Neville, Chris Peterson, Patrick Shipman, and Lori Ziegelmeier.
[arXiv:1507.06217,
Abstract]

Many datasets can be viewed as a noisy sampling of an underlying space, and tools from topological data analysis can characterize this structure for the purpose of knowledge discovery. One such tool is persistent homology, which provides a multiscale description of the homological features within a dataset. A useful representation of this homological information is a persistence diagram (PD). Efforts have been made to map PDs into spaces with additional structure valuable to machine learning tasks. We convert a PD to a finitedimensional vector representation which we call a persistence image (PI), and prove the stability of this transformation with respect to small perturbations in the inputs. The discriminatory power of PIs is compared against existing methods, showing significant performance gains. We explore the use of PIs with vectorbased machine learning tools, such as linear sparse support vector machines, which identify features containing discriminating topological information. Finally, high accuracy inference of parameter values from the dynamic output of a discrete dynamical system (the linked twist map) and a partial differential equation (the anisotropic KuramotoSivashinsky equation) provide a novel application of the discriminatory power of PIs.
We use the nudged elastic band method from computational chemistry to analyze highdimensional data. Our approach is inspired by Morse theory, and as output we produce an increasing sequence of small cell complexes modeling the dense regions of the data. We test the method on data sets arising in social networks and in image processing. Furthermore, we apply the method to identify new topological structure in a data set of optical flow patches.
Carlsson, Ishkanov, de Silva, and Zomorodian apply computational topological tools to the data set of 3 × 3 patches from optical images studied by Lee, Pedersen, and Mumford and find geometric structures for high density subsets. One high density subset is called the primary circle and essentially consists of patches with a line separating a light and a dark region. In this paper, we apply the techniques of Carlsson et al. to range patches. By enlarging to 5 × 5 and 7 × 7 patches, we find core subsets that have the topology of the primary circle, suggesting a stronger connection between optical patches and range patches than was found by Lee, Pedersen, and Mumford.
Conference proceedings
The computation of persistent homology has proven a fundamental component of the nascent field of topological data analysis and computational topology. We describe a new software package for topological computation, with design focus on needs of the research community. This tool, replacing previous jPlex and Plex, enables researchers to access state of the art algorithms for persistent homology, cohomology, hom complexes, filtered simplicial complexes, filtered cell complexes, witness complex constructions, and many more essential components of computational topology. We describe the design goals we have chosen, the resulting software package, and some of its more novel capabilities.
Software tutorials