Browsing by Author "Harer, John"

This dissertation places intersection homology and local homology within the framework of persistence, which was originally developed for ordinary homology by Edelsbrunner, Letscher, and Zomorodian. The eventual goal, begun but not completed here, is to provide analytical tools for the study of embedded stratified spaces, as well as for high-dimensional and possibly noisy datasets for which the number of degrees of freedom may vary across the parameter space. Specifically, we create a theory of persistent intersection homology for a filtered stratified space and prove several structural theorems about the pair groups asso- ciated to such a filtration. We prove the correctness of a cubic algorithm which computes these pair groups in a simplicial setting. We also define a series of intersec- tion homology elevation functions for an embedded stratified space and characterize their local maxima in dimension one. In addition, we develop a theory of persistence for a multi-scale analogue of the local homology groups of a stratified space at a point. This takes the form of a series of local homology vineyards which allow one to assess the homological structure within a one-parameter family of neighborhoods of the point. Under the assumption of dense sampling, we prove the correctness of this assessment at a variety of radius scales.

This dissertation extends the theory of persistent homology to time varying systems. Most of the previous work has been dedicated to using this powerful tool in topological data analysis to study static point clouds. In particular, given a point cloud, we can construct its persistence diagram. Since the diagram varies continuously as the point cloud varies continuously, we study the space of time varying persistence diagrams, called vineyards when they were introduced by Cohen-Steiner, Edelsbrunner, and Morozov.

We will first show that with a good choice of metric, these vineyards are stable for small perturbations of their associated point clouds. We will also define a new mean for a set of persistence diagrams based on the work of Mileyko et al. which, unlike the previously defined mean, is continuous for geodesic vineyards.

Next, we study the sensor network problem posed by Ghrist and de Silva, and their application of persistent homology to understand when a set of sensors covers a given region. Giving each of these sensors a probability of failure over time, we show that an exact computation of the probability of failure of the whole system is NP-hard, but give an algorithm which can predict failure in the case of a monitored system.

Finally, we apply these methods to an automated system which can cluster agents moving in aerial images by their behaviors. We build a data structure for storing and querying the information in real-time, and define behavior vectors which quantify behaviors of interest. This clustering by behavior can be used to find groups of interest, for which we can also quantify behaviors in order to determine whether the group is working together to achieve a common goal, and we speculate that this work can be extended to improving tracking algorithms as well as behavioral predictors.

This work introduces geometric and topological data analysis (TDA) tools that can be used in conjunction with sliding window transformations, also known as delay-embeddings, for discovering structure in time series and dynamical systems in an unsupervised or supervised learning framework. For signals of unknown period, we introduce an intuitive topological method to discover the period, and we demonstrate its use in synthetic examples and real temperature data. Alternatively, for almost-periodic signals of known period, we introduce a metric called Geometric Complexity of an Almost Periodic signal (GCAP), based on a topological construction, which allows us to continuously measure the evolving variation of its periods. We apply this method to temperature data collected from over 200 weather stations in the United States and describe the novel patterns that we observe. Next, we show how geometric and TDA tools can be used in a supervised learning framework. Seizure-detection using electroencephalogram (EEG) data is formulated as a binary classification problem. We define new collections of geometric and topological features of multi-channel data, which utilizes temporal and spatial context of EEG, and show how it results in better overall performance of seizure detection than using the usual time-domain and frequency domain features. Finally, we introduce a novel method to sonify persistence diagrams, and more generally any planar point cloud, using a modified version of the harmonic table. This auditory display can be useful for finding patterns that visual analysis alone may miss.

Importance

Objective

Design setting and participants

Main outcomes and measures

Results

Conclusions and relevance

We work on constructing mathematical models of gene regulatory networks for periodic processes, such as the cell cycle in budding yeast, using biological data sets and applying or developing analysis methods in the areas of mathematics, statistics, and computer science. We identify genes with periodic expression and then the interactions between periodic genes, which defines the structure of the network. This network is then translated into a mathematical model, using Ordinary Differential Equations (ODEs), to describe these entities and their interactions. The models currently describe gene regulatory interactions, but we are expanding to capture other events, such as phosphorylation and ubiquitination. To model the behavior, we must then find appropriate parameters for the mathematical model that allow its dynamics to approximate the biological data.

This pipeline for model construction is not focused on a specific algorithm or data set for each step, but instead on leveraging several sources of data and analysis from several algorithms. For example, we are incorporating data from multiple time series experiments, genome-wide binding experiments, computationally predicted binding, and regulation inference to identify potential regulatory interactions.

These approaches are designed to be applicable to various periodic processes in different species. While we have worked most extensively on models for the cell cycle in Saccharomyces cerevisiae, we have also begun working with data sets for the metabolic cycle in S. cerevisiae, and the circadian rhythm in Mus musculus.

Switching networks are a common model for biological systems, especially

for genetic transcription networks. Stuart Kaufman originally proposed

the usefulness of the Boolean framework, but much of the dynamical

features there are not realizable in a continuous analogue. We introduce the notion

of braid-like dynamics as a bridge between Boolean and continuous dynamics and

study its importance in the local dynamics of ring and ring-like networks. We discuss

a near-theorem on the global dynamics of general feedback networks, and in the final

chapter study the main ideas of this thesis in models of a yeast cell transcription network.

This thesis provides a new take on problems in multimedia times series analysis by using a shape-based perspective to quantify patterns in time, which is complementary to more traditional analysis-based time series techniques. Inspired by the dynamical systems community, we turn time series into shapes via sliding window embeddings, which we refer to as ``time-ordered point clouds'' (TOPCs). This framework has traditionally been used on a single 1D observation function for deterministic systems, but we generalize the sliding window technique so that it not only applies to multivariate data (e.g. videos), but that it also applies to data which is not stationary (e.g. music).

The geometry of our time-ordered point clouds can be quite informative. For periodic signals, the point clouds fill out topological loops, which, depending on harmonic content, reside on various high dimensional tori. For quasiperiodic signals, the point clouds are dense on a torus. We use modern tools from topological data analysis (TDA) to quantify degrees of periodicity and quasiperiodicity by looking at these shapes, and we show that this can be used to detect anomalies in videos of vibrating vocal folds. In the case of videos, this has the advantage of substantially reducing the amount of preprocessing, as no motion tracking is needed, and the technique operates on raw pixels. This is also one of the first known uses of persistent H2 in a high dimensional setting.

Periodic processes represent only a sliver of possible dynamics, and we also show that sequences of arbitrary normalized sliding window point clouds are approximately isometric between ``cover songs,'' or different versions of the same song, possibly with radically different spectral content. Surprisingly, in this application, an incredibly simple geometric descriptor based on self-similarity matrices performs the best, and it also enables us to use MFCC features for this task, which was previously thought not to be possible due to significant timbral differences that can exist between versions. When combined with traditional pitch-based features using similarity metric fusion, we obtain state of the art results on automatic cover song identification.

In addition to being used as a geometric descriptor, self-similarity matrices provide a unifying description of phenomena in time-ordered point clouds throughout our work, and we use them to illustrate properties such as recurrence, mirror symmetry in time, and harmonics in periodic processes. They also provide the base representation for designing isometry blind time warping algorithms, which we use to synchronize time-ordered point clouds that are shifted versions of each other in space without ever having to do a spatial alignment. In particular, we devise an algorithm that lower bounds the 1-stress between two time-ordered point clouds, which is related to the Gromov-Hausdorff distance.

Overall, we show a proof-of-concept and promise of the nascent field of geometric signal processing, which is worthy of further study in applications of music structure, multimodal data analysis, and video analysis.

The work presented in this dissertation includes the study of cohomology and cohomological operations within the framework of Persistence. Although Persistence was originally defined for homology, recent research has developed persistent approaches to other algebraic topology invariants. The work in this document extends the field of persistence to include cohomology classes, cohomology operations and characteristic classes.

By starting with presenting a combinatorial formula to compute the Stiefel-Whitney homology class, we set up the groundwork for Persistent Characteristic Classes. To discuss persistence for the more general cohomology classes, we construct an algorithm that allows us to find the Poincar'{e} Dual to a homology class. Then, we develop two algorithms that compute persistent cohomology, the general case and one for a specific cohomology class. We follow this with defining and composing an algorithm for extended persistent cohomology.

In addition, we construct an algorithm for determining when a cohomology class is decomposible and compose it in the context of persistence. Lastly, we provide a proof for a concise formula for the first Steenrod Square of a given cohomology class and then develop an algorithm to determine when a cohomology class is a Steenrod Square of a lower dimensional cohomology class.

This dissertation focuses on Boolean networks with a view to their applications in Systems Biology. We study two notions of stability, based on Hamming distance and on maintenance of a stable period length. Algorithms are given for the determination of Boolean networks from both complete and partial dynamics. The dynamics of ring networks are systematically studied. An algebraic structure is developed for derivation of adjacency matrices for the dynamics of Boolean networks from simple building blocks, both by edge-swapping and by gluing simple building blocks. Some results are implemented in Python and conclusions drawn for theta networks, a class of networks only slightly more complex than rings. A short section on applications to a known biological system closes the dissertation.