Henry Adams
Research
My research interests are in computational topology and geometry, combinatorial topology, and applied topology. In particular, I like to study VietorisRips and Čech simplicial complexes, VietorisRips and Čech metric thickenings, applications of topology to data analysis, and applications of topology to sensor networks.
I am the codirector of the Applied Algebraic Topology Research Network, which hosts a weekly Online Seminar. Recordings of our seminar are available at our YouTube Channel, which has over 1,000 YouTube subscribers, and averages over 2,000 hours watched per year.
At Colorado State I am a a coorganizer of the Topology Seminar, a member of the Pattern Analysis Lab, and an attendee of the Algebraic Combinatorics Seminar and the Data Science Seminar.
I am a member of the Descriptors of Energy Landscapes Using Topological Data Analysis (DELTA) leadership team.
Here is my PhD thesis, a related research highlight, and research statements from 2020, 2019, 2018, 2017, 2016.
See section 4 of this column for some open (and some "closed") problems I am interested in.
Preprints


An adaptation for iterative structured matrix completion.
With Lara Kassab and Deanna Needell.
Submitted (2020).
[arXiv:2002.02041,
Abstract]

In today's datadriven world, data completion is essential whether it is the main goal or a preprocessing step. Structured matrix completion includes any setting in which data is not missing uniformly at random. In recent work, a modification to the standard nuclear norm minimization (NNM) for matrix completion has been developed to take into account sparsitybased structure in the missing entries. This notion of structure is motivated in many settings including recommender systems, where the probability that an entry is observed or not depends on the value of the entry. We propose adjusting an Iteratively Reweighted Least Squares (IRLS) algorithm for lowrank matrix completion to take into account sparsitybased structure in the missing entries. We also present an iterative gradientprojectionbased implementation of the algorithm that can handle largescale matrices. Finally, we present a robust array of numerical experiments on matrices of varying sizes, ranks, and level of structure. We show that our proposed method is comparable with the adjusted NNM on small structured matrices. Further, we show that our proposed method often outperforms the IRLS algorithm in structured settings on matrices up to size 1000×1000.


Topological data analysis of collective motion.
With MariaVeronica Ciocanel, Chad M. Topaz, and Lori Ziegelmeier.
SIAM News, January/February Issue (2020).
[Publisher Link,
Print Version]



Chapter on Topological data analysis.
With Johnathan Bush and Joshua Mirth, in the book Data Science for Mathematicians, editor Nathan Carter, Taylor & Francis (2020).

A VietorisRips complex is a way to thicken a (possibly discrete) metric space into a larger space containing more topological information. We prove that if C is a convex closed differentiable curve in the plane such that the convex hull of C contains the evolute of C, then the homotopy type of a VietorisRips complex of a subset of n points from C can be computed in time O(n log n). Furthermore, we show how to compute the kdimensional persistent homology of these n points in running time O(n^{2}(k+log n)), which is nearly quadratic in the number of vertices n. This improves upon the traditional persistent homology algorithm, which is cubic in the number of simplices of dimension at most k+1, and hence of running time O(n^{3(k+2)}) in the number of vertices n. We ask if there are other geometric settings in which computing persistent homology is (say) quadratic or cubic in the number of vertices, instead of in the number of simplices.
Persistent homology has emerged as a novel tool for data analysis in the past two decades. However, there are still very few shapes or even manifolds whose persistent homology barcodes (say of the VietorisRips complex) are fully known. Towards this direction, let P_{n} be the boundary of a regular polygon in the plane with n sides; we describe the homotopy types of VietorisRips complexes of P_{n}. Indeed, when n=(2k+1)!! is an odd double factorial, we provide a complete characterization of the homotopy types and persistent homology of the VietorisRips complexes of P_{n} up to a scale parameter r_{n}, where r_{n} approaches the diameter of P_{n} as n tends to infinity. Surprisingly, these homotopy types include spheres of all dimensions. Roughly speaking, the number of higherdimensional spheres appearing is linked to the number of equilateral (but not necessarily equiangular) stars that can be inscribed into P_{n}. As our main tool we use the recentlydeveloped theory of cyclic graphs and winding fractions. Furthermore, we show that the VietorisRips complex of an arbitrarily dense subset of P_{n} need not be homotopy equivalent to the VietorisRips complex of P_{n} itself, and indeed, these two complexes can have different homology groups in arbitrarily high dimensions. As an application of our results, we provide a lower bound on the GromovHausdorff distance between P_{n} and the circle.
Research papers


Metric thickenings and group actions.
With Mark Heim and Chris Peterson.
Accepted to appear in the Journal of Topology and Analysis (2020).
[arXiv:1911.00732,
Abstract]

Let G be a group acting properly and by isometries on a metric space X; it follows that the quotient or orbit space X/G is also a metric space.
We study the VietorisRips and Čech complexes of X/G.
Whereas (co)homology theories for metric spaces let the scale parameter of a VietorisRips or Čech complex go to zero, and whereas geometric group theory requires the scale parameter to be sufficiently large, we instead consider intermediate scale parameters (neither tending to zero nor to infinity).
As a particular case, we study the VietorisRips and Čech thickenings of projective spaces at the first scale parameter where the homotopy type changes.


Operations on metric thickenings.
With Johnathan Bush and Joshua Mirth.
Accepted for a keynote presentation at the Applied Category Theory remote conference, and to be published in its accompanying volume in Electronic Proceedings in Theoretical Computer Science (2020).
[Paper accepted to EPTCS,
Abstract]

Many simplicial complexes arising in practice have an associated metric space structure on the vertex set but not on the complex, e.g. the VietorisRips complex in applied topology.
We formalize a remedy by introducing a category of simplicial metric thickenings whose objects have a natural realization as metric spaces.
The properties of this category allow us to prove that, for a large class of thickenings including VietorisRips and Čech thickenings, the product of metric thickenings is homotopy equivalent to the metric thickenings of product spaces, and similarly for wedge sums.
Thickenings of a metric space capture local geometric properties of the space. Here we exhibit applications of lower bounding the topology of thickenings of the circle and more generally the sphere. We explain interconnections with the geometry of circle actions on Euclidean space, the structure of zeros of trigonometric polynomials, and theorems of BorsukUlam type. We use the combinatorial and geometric structure of the convex hull of orbits of circle actions on Euclidean space to give geometric proofs of the homotopy type of metric thickenings of the circle.
Homotopical connectivity bounds of thickenings of the sphere allow us to prove that a weighted average of function values of odd maps S^{n} → R^{n+2} on a small diameter set is zero. We prove an additional generalization of the BorsukUlam theorem for odd maps S^{2n1} → R^{2kn+2n1}. We prove such results for odd maps from the circle to any Euclidean space with optimal quantitative bounds. This in turn implies that any raked homogeneous trigonometric polynomial has a zero on a subset of the circle of a specific diameter; these results are optimal.


A fractal dimension for measures via persistent homology.
With Manuchehr Aminian, Elin Farnell, Michael Kirby, Chris Peterson, Joshua Mirth, Rachel Neville, and Clayton Shonkwiler.
In: Baas N., Carlsson G., Quick G., Szymik M., Thaule M. (eds), Topological Data Analysis. Abel Symposia, vol 15. Springer (2020).
[Publisher Link,
arXiv:1808.01079,
Abstract,
Software]

We use persistent homology in order to define a family of fractal dimensions, denoted dim_{PH}^{i}(μ) for each homological dimension i ≥ 0, assigned to a probability measure μ on a metric space.
The case of 0dimensional homology (i=0) relates to work by Michael J Steele (1988) studying the total length of a minimal spanning tree on a random sampling of points.
Indeed, if μ is supported on a compact subset of Euclidean space R^{m} for m ≥ 2, then Steele's work implies that dim_{PH}^{0}(μ)=m if the absolutely continuous part of μ has positive mass, and otherwise dim_{PH}PH^{0}(μ)<m.
Experiments suggest that similar results may be true for higherdimensional homology 0<i<m, though this is an open question.
Our fractal dimension is defined by considering a limit, as the number of points n goes to infinity, of the total sum of the idimensional persistent homology interval lengths for n random points selected from μ in an i.i.d. fashion.
To some measures μ, we are able to assign a finer invariant, a curve measuring the limiting distribution of persistent homology interval lengths as the number of points goes to infinity.
We prove this limiting curve exists in the case of 0dimensional homology when n is the uniform distribution over the unit interval, and conjecture that it exists when n is the rescaled probability measure for a compact set in Euclidean space with positive Lebesgue measure.


On homotopy types of VietorisRips complexes of metric gluings.
With Michał Adamaszek, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier.
Journal of Applied and Computational Topology (2020), https://doi.org/10.1007/s4146802000054y.
Conference version VietorisRips and Čech complexes of metric gluings in Proceedings of the 34th Symposium on Computational Geometry (2018), 3:13:15.
[Journal Version Link,
Conference Version Link,
arXiv:1712.06224,
Abstract,
Slides]

We study VietorisRips and Čech complexes of metric wedge sums and metric gluings. We show that the VietorisRips (resp. Čech) complex of a wedge sum, equipped with a natural metric, is homotopy equivalent to the wedge sum of the VietorisRips (resp. Čech) complexes. We also provide generalizations for certain metric gluings, i.e. when two metric spaces are glued together along a common isometric subset. As our main example, we deduce the homotopy type of the VietorisRips complex of two metric graphs glued together along a sufficiently short path. As a result, we can describe the persistent homology, in all homological dimensions, of the VietorisRips complexes of a wide class of metric graphs.
Multidimensional scaling (MDS) is a popular technique for mapping a finite metric space into a lowdimensional Euclidean space in a way that best preserves pairwise distances.
We overview the theory of classical MDS, along with its optimality properties and goodness of fit.
Further, we present a notion of MDS on infinite metric measure spaces that generalizes these optimality properties.
As a consequence we can study the MDS embeddings of the geodesic circle S^{1} into R^{m} for all m, and ask questions about the MDS embeddings of the geodesic nspheres S^{n} into R^{m}.
Furthermore, we address questions on convergence of MDS.
For instance, if a sequence of metric measure spaces converges to a fixed metric measure space X, then in what sense do the MDS embeddings of these spaces converge to the MDS embedding of X?


A torus model for optical flow.
With Johnathan Bush, Brittany Carr, Lara Kassab, and Joshua Mirth.
Journal version published in Pattern Recognition Letters 129 (2020), 304310.
Conference version On the nonlinear statistics of optical flow published in Proceedings of Computational Topology in Image Context, LNCS volume 11382 (2019), 151165.
[Journal Version Link,
Conference Version Link,
arXiv:1812.00875,
Abstract,
Slides,
Software]

We propose a torus model for highcontrast patches of optical flow.
Our model is derived from a database of groundtruth optical flow from the computergenerated video Sintel, collected by Butler et al. in A naturalistic open source movie for optical flow evaluation.
Using persistent homology and zigzag persistence, popular tools from the field of computational topology, we show that the highcontrast 3×3 patches from this video are wellmodeled by a torus, a nonlinear 2dimensional manifold.
Furthermore, we show that the optical flow torus model is naturally equipped with the structure of a fiber bundle, related to the statistics of range image patches.
Given a sample X from an unknown manifold M embedded in Euclidean space, it is possible to recover the homology groups of M by building a VietorisRips or Čech simplicial complex on top of the vertex set X. However, these simplicial complexes need not inherit the metric structure of the manifold, in particular when X is infinite. Indeed, a simplicial complex is not even metrizable if it is not locally finite. We instead consider metric thickenings of X, called the VietorisRips and Čech thickenings, which are equipped with the 1Wasserstein metric in place of the simplicial complex topology. We show that for Euclidean subsets M with positive reach, the thickenings satisfy metric analogues of Hausmann's theorem and the nerve lemma (the metric VietorisRips and Čech thickenings of M are homotopy equivalent to M for scale parameters less than the reach). In contrast to Hausmann's original result, our homotopy equivalence is a deformation retraction, is realized by canonical maps in both directions, and furthermore can be proven to be a homotopy equivalence via simple linear homotopies from the map compositions to the corresponding identity maps.
For X a metric space and r > 0 a scale parameter, the VietorisRips complex VR_{<}(X;r) (resp. VR_{≤}(X;r)) has X as its vertex set, and a finite subset σ of X as a simplex whenever the diameter of σ is less than r (resp. at most r). Though VietorisRips complexes have been studied at small choices of scale by Hausmann and Latschev, they are not wellunderstood at larger scale parameters. In this paper we investigate the homotopy types of VietorisRips complexes of ellipses Y={(x,y) ∈ R^{2}  (x/a)^{2}+y^{2}=1} of small eccentricity, meaning 1 < a ≤ √2. Indeed, we show there are constants r_{1} < r_{2} such that for all r_{1} < r < r_{2}, we have VR_{<}(Y;r) ≃ S^{2} and VR_{≤}(X;r) ≃ ∨^{5} S^{2}, though only one of the twospheres in VR_{≤}(X;r) is persistent. Furthermore, we show that for any scale parameter r_{1} < r < r_{2}, there are arbitrarily dense subsets of the ellipse such that the VietorisRips complex of the subset is not homotopy equivalent to the VietorisRips complex of the entire ellipse. As our main tool we link these homotopy types to the structure of infinite cyclic graphs.
Given a sample of points X in a metric space M and a scale r > 0, the VietorisRips simplicial complex VR(X;r) is a standard construction to attempt to recover M from X up to homotopy type. A deficiency of this approach is that VR(X;r) is not metrizable if it is not locally finite, and thus does not recover metric information about M. We attempt to remedy this shortcoming by defining a metric space thickening of X, which we call the VietorisRips thickening VR^{m}(X;r), via the theory of optimal transport. When M is a complete Riemannian manifold, or alternatively a compact Hadamard space, we show that the VietorisRips thickening satisfies Hausmann's theorem (VR^{m}(M;r) ≃ M for r sufficiently small) with a simpler proof than Hausmann's original result: homotopy equivalence VR^{m}(M;r) → M is canonically defined as a center of mass map, and its homotopy inverse is the (now continuous) inclusion map M ↪ VR^{m}(M;r). Furthermore, we describe the homotopy type of the VietorisRips thickening of the nsphere at the first positive scale parameter r where the homotopy type changes.


Sweeping costs of planar domains.
With Brooks Adams and Colin Roberts.
In Erin W Chambers, Brittany T Fasy, and Lori Ziegelmeier, eds., Research in Computational Topology, pages 7192, AWM Springer series, volume 13 (2018).
[Publisher Link,
arXiv:1612.03540,
Abstract]

Let D be a Jordan domain in the plane. We consider a pursuitevasion, contamination clearing, or sensor sweep problem in which the pursuer at each point in time is modeled by a continuous curve, called the sensor curve. Both time and space are continuous, and the intruders are invisible to the pursuer. Given D, what is the shortest length of a sensor curve necessary to provide a sweep of domain D, so that no continuouslymoving intruder in D can avoid being hit by the curve? We define this length to be the sweeping cost of D. We provide an analytic formula for the sweeping cost of any Jordan domain in terms of the geodesic Fréchet distance between two curves on the boundary of D with nonequal winding numbers. As a consequence, we show that the sweeping cost of any convex domain is equal to its width, and that a convex domain of unit area with maximal sweeping cost is the equilateral triangle.


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.
Journal of Machine Learning Research 18 (2017), Number 8, 135.
[PDF of Paper,
Publisher Link,
arXiv:1507.06217,
Abstract,
Software]

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.
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.
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.
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).
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.
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.
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.
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.
Software tutorials
Mathematica demonstrations
The following interactive Mathematica demonstrations allow one to visualize geometric simplicial complexes at various choices of scale. The user can click on the points to move them around, add new points, delete points, and vary the scale parameter via a slider. Thanks to Jan Segert for help in creating these demonstrations!
What is topology? What are simplicial complexes?
Topology is the study of shapes and surfaces in higher dimensions. One way to build a higherdimensional space is by gluing simple building blocks together. For example, you can start with a set of vertices (0dimensional building blocks), glue on a set of edges (1dimensional building blocks), glue on a set of triangles (2dimensional building blocks), and then glue on a set of tetrahedra (3dimensional building blocks). But the fun doesn't stop there  you can continue by gluing on higherdimensional pieces, to form what's called a simplicial complex. I think of this like building a LEGO set. When creating a LEGO set, you follow a list of instructions describing how to attach simple building blocks together. Once done, you can simply look at the LEGO set you built to see and understand its shape. In topology, you are sometimes given a list of instructions for how to glue higherdimensional building block together. Once done, we can't understand the higherdimensional shape by simply looking at it, but we can use mathematics to help us visualize the shape we built!