Randomness in Topology and its Applications

We introduce a novel procedure that, given sparse data generated from a stationary deterministic nonlinear dynamical system, can characterize specific local and/or global dynamic behavior with rigorous probability guarantees. More precisely, the sparse data is used to construct a statistical surrogate model based on a Gaussian process (GP). The dynamics of the surrogate model is interrogated using combinatorial methods and characterized using algebraic topological invariants (Conley index). The GP predictive distribution provides a lower bound on the confidence that these topological invariants, and hence the characterized dynamics, apply to the unknown dynamical system (a sample path of the GP).

We discuss ways of probing the shape of data in metric spaces using metric observables (1-Lipschitz functions). This leads to a dimension reduction, data visualization, and statistical analysis technique that we call Principal Observable Analysis. We also discuss the construction of robust data summaries associated with such metric observables in the form of filtered merge trees, Reeb graphs, and Leray-Reeb pre-cosheaves.

Homology features of spaces which appear in applications, for instance 3D meshes, are among the most important topological properties of these objects. Given a non-trivial cycle in a homology class, we consider the problem of computing a representative in that homology class which is optimal. We study two measures of optimality, namely, the lexicographic order of cycles (the lex-optimal cycle) and the bottleneck norm (a bottleneck-optimal cycle). We give a simple algorithm for computing the lex-optimal cycle for a 1-homology class in a closed orientable surface. In contrast to this, our main result is that, in the case of 3-manifolds of size n² in the Euclidean 3-space, the problem of finding a bottleneck optimal cycle cannot be solved more efficiently than solving a system of linear equations with an n × n sparse matrix. From this reduction, we deduce several hardness results. Most notably, we show that for 3-manifolds given as a subset of the 3-space of size n², persistent homology computations are at least as hard as rank computation (for sparse matrices) while ordinary homology computations can be done in O(n² log n) time. To the best of our knowledge, this is the first such distinction between these two computations. Moreover, it follows that the same disparity exists between the height persistent homology computation and general sub-level set persistent homology computation for simplicial complexes in 3-space.

The Eden cell growth model is a simple discrete stochastic process which produces a “blob” in Rd: start with one cube in the regular grid, and at each time step add a neighboring cube uniformly at random. This process has been used as a model for the growth of aggregations, tumors, and bacterial colonies and the healing of wounds, among other natural processes. Here, we study the topology and local geometry of the resulting structure, establishing asymptotic bounds for Betti numbers. Our main result is that the Betti numbers at time t grow at a rate between t(d-1)/d and Pd(t), where Pd(t) is the size of the site perimeter. Assuming a widely believed conjecture, this establishes the rate of growth of the Betti numbers in every dimension. We also present the results of computational experiments on finer aspects of the geometry and topology, such as persistent homology and the distribution of shapes of holes.
This research is joint work with Fedor Manin and Érika Roldán.

We introduce a model of random chain complex over the reals. The main question we are interested in is: what does the homology of such a random chain complex typically look like? We show that under various hypothesis, homology tries to be as small as possible. This is joint work in progress with Ayat Ababneh.

There are many ways of defining persistence diagrams. In this talk I will discuss the definition based on the Mobius inversion function which was introduced by Amit Patel under the name Generalized Persistence Diagrams. I will cover how this approach has appeared implicitly and explicitly in various results on persistence as well as various implications of this approach and (very) new developments. In particular, I will cover a surprising connection between Euler characteristics and persistence diagrams.  This is joint work with Amit Patel.

Random field theory (RFT) has proven successful at understanding the null behavior of smooth random fields under the null / centered model. The main tool used in such analyses is the Kac-Rice formula that essentially enables description of a Palm theory for the process. Using the Kac-Rice framework, we consider inference in models derived from the critical points of the process itself.

Persistent homology, the flagship method of topological data analysis, can be used to provide a quantitative summary of the shape of data. One way to pass data to this method is to start with a finite, discrete metric space (whether or not it arises from a Euclidean embedding) and to study the resulting filtration of the Rips complex. In this talk, we will discuss several available methods for turning a time series into a discrete metric space, such as the Takens embedding, k-nearest neighbor network, and ordinal partition network. Combined with persistent homology and machine learning methods, we show how this can be used to classify behavior and investigate bifurcations from time series in both synthetic and experimental data.

Persistent homology is well-defined and well studied for tame functions, for example various ones arising from finite point sets. However, periodic functions — for example used to study periodic point sets, like the atoms of a crystal — are not tame. We therefore extend the definition of persistent homology to periodic functions, which is a non-trivial endeavor. In contrast to related work, we quantify how the multiplicities of persistence pairs tend to infinity with increasing window size, in a way that is stable under perturbations and invariant under different finite representations of the infinite periodic function. This project is still ongoing research, but I’ll explain what we already know and what we don’t know yet.

The recent curation of large-scale databases with 3D surface scans of shapes has motivated the development of computational tools that better detect global patterns in morphological variation. Recent studies have focused on developing methods for the task of sub-image selection which aims at identifying physical features that best describe the variation between classes of 3D objects. A large piece in assessing the utility of these approaches is to demonstrate their performance on both simulated and real datasets. However, when creating a model for shape statistics, real data can be difficult to access and the sample sizes within these data are often small due to expensive collection procedures. Meanwhile, the landscape of current shape simulation methods has been mostly limited to approaches that use black-box inference—making it difficult to systematically assess the power and calibration of sub-image models. In this talk, we present a new statistical framework for simulating realistic 2D and 3D shapes based on probability distributions which can be learned from real data. We demonstrate this framework in two applications within computational biology: (1) cellular imagining of neutrophils and (2) mandibular molars from four different suborders of primates.

Robust topological information commonly comes in the form of a set of persistence diagrams that can be seen as discrete measures and are uneasy to use in generic machine learning frameworks. 

In this talk we will introduce a fast, learnt, unsupervised vectorization method for measures in Euclidean spaces and use it for clustering of distributions of discrete measures. The algorithm is simple and efficiently discriminates important space regions where meaningful differences to the ‘’mean’’ measure arise. Applied to persistence diagrams, we will show that it is proven to be able to separate clusters of persistence diagrams. We will illustrate the strength and robustness of our approach on a few synthetic and real data sets.  

Bifurcations in a dynamical system are drastic behavioral changes, thus being able to detect the parameter values for which these bifurcations occur is essential to understanding the system overall. We develop a one-step method to study and detect bifurcations using zigzag persistent homology. While standard persistent homology has been used in this setting, it usually requires analyzing a collection of persistence diagrams, which in turn drives up the computational cost. Using zigzag persistence, we can capture topological changes in the state space of the dynamical system in only one persistence diagram.

Graphs and network data are ubiquitous across a wide spectrum of scientific and application domains. Often in practice, an input graph can be considered as an observed snapshot of a (potentially continuous) hidden domain or process. Subsequent analysis and inferences are then performed on this observed graph. In this talk, we will describe a natural network model: we assume that there is a true grpah wihch is a certain proximity graph for points sampled from a nice domain. Then the observed graph is an Erdos-Renyi (ER) type perturbed version of that true graph, where random edges can be inserted and deleted. We will describe two main results obtained: the first concerns the recovery of shortest path metric of the true graph from this ER-perturbed graph. The second concerns the behavior of the so-called clique number of the graph. This is joint work with M. Kahle, S. Parthasarathy, S. Sivakoff, and M. Tian.

The global structure of edge flows, alternating functions on graph edges, and their simplicial extensions can be characterized via projection onto principled subspaces associated with graph operators. Classically, the edge-incidence matrix acts as a discrete gradient whose associated subspaces are widely used to decompose an edge flow into a conservative and rotational component. Simplicial homology extends this idea to complexes via chains of operators that map between simplices of neighboring dimension. The expected structure of randomly sampled functions is determined by the covariance of the sampled function, and the projector onto the associated subspace. We analyze the relation between expected structure, covariance, and graph topology, by expanding both the covariance and the projector onto powers of a weighted adjacency matrix defined by the operator and its adjoint. We show that, in this basis, the expected structure is easily interpreted using the coefficients of the associated power series, and that truncating the series can produce accurate approximations even when the graph topology is not known exactly. We then study the spectral characteristics of graph families that enable approximation with a small number of terms.