Workshop on Computational Topology at SoCG 2012

Title: Topological measures of similarity

Abstract:
The question of how to measure similarity between curves in various topological spaces has received much attention recently. Possibilities for comparing curves include the Frechet distance (and its variants such as geodesic, homotopic, and isotopic Frechet distance), homotopy height, and deformation area (or the area of the homotopy); many of these have algorithms in settings that range from the plane to combinatorial surfaces to cell complexes. We will compare and survey known results as well as recent progress and open questions in several of these settings.

Title: Simplification of simplicial complexes, towards the intrinsic dimension

Abstract:
Given a set of points that sample a shape, it has been proved recently that under some density requirements the Rips complex of the points provides an approximation of the shape with the correct homotopy type.

One advantage of the Rips complex is that it is determined entirely by its 1-skeleton which provides a compact form of storage. Unfortunately, the dimension of the Rips complex can be huge, compared to the intrinsic dimension of the shape.

We will describe different strategies for simplifying the Rips complex and obtain a simplicial complex whose dimension is that of the sampled shape. In particular, we will present the beginning of some theorical work which aims at explaining the good behaviour of our simplification strategies in practice.

Title: Algebraic Persistence

Abstract:
Persistent homology was shown by Zomorodian and Carlsson to be accurately modeled as homology with coefficients in the polynomial ring k[t]. Much of the body of work in the community since these results has assumed free chain complexes: torsion on a chain level remains an essentially unsolved problem.

We develop ideas from computational commutative algebra to produce purely algebraic tools to approach persistence modules. These ideas provide purely algebraic approaches to the computation of finite presentations of various modules, such as images, kernels and cokernels of maps between persistence modules, paralleling work by Cohen-Steiner, Edelsbrunner, Harer and Morozov. The algebraic approach produces two tangible benefits: chain complexes with torsion are clear to handle, and with this, relative homology -- and with this, both local and extended persistent homology -- becomes accessible without relying on long exact sequences or on cone constructions.

(Joint work with Primoz Skraba.)

Title: Consistent scale selection for exploratory visualization and analysis of data sets

Abstract:
Choosing an appropriate scale is a frequently encountered problem in data analysis, and paradigms in the field support both the choice of strategies to make smart, definite choices and the hierarchical or persistence approach of looking at all scales at once. In the core of the “Mapper” algorithm for visualization and analysis of point cloud data, a scale choice must be made multiple times for overlapping fragments of the data set. We present the concept of a scale graph, where scale choices in neighboring regions are brought into conjunction to make consistent decisions at local scale, while retaining global flexibility. By selecting an optimal path through the scale graph, we can make more plausible choices, overcome existing weaknesses, validate results more easily and simplify the data analysis process for the user.

(Joint work with Gunnar Carlsson, Facundo Mémoli, Gurjeet Singh.)

Title: On the Stability of Preimages

Abstract:
Given a real valued map, persistence allows one to quantify the stability of the homology of its sublevel sets to perturbations of the map. Given a continuous map to a manifold M and a point p in M, how stable is the homology of the preimage of p? The well group addresses this basic question. Using pictures, I will motivate this question and introduce the basic definitions.

Title: Persistence of Extra Modes in Gaussian Mixtures

Abstract:
The sum of finitely many isotropic Gaussian kernels in 2- or higher-dimensional Euclidean space can have more modes than kernels. Even more surprising is the fact that the sum can have an exponential number of critical values. We consider the sum of Gaussians where the means of the Gaussians are located at the vertices of a regular n-simplex in R^n. Normalizing the mixture to obtain a probability distribution, we focus our attention on the extra mode that appears at the barycenter of the simplex. In particular, we investigate how the persistence of the mode at the barycenter changes with respect to increasing dimension.

Title: Computing persistence for simplicial maps and its application to Rips complexes

Abstract:
It is known that persistent homology and zigzag persistent homology are well defined for homology modules where homomorphisms need not be induced by inclusion maps. However, there are no practical algorithms for general homology homomorphisms except the algorithm in Gunnar Carlsson and Vin De Silva [2008] which works by operating on the matrices representing the homomorphisms. In this talk, we propose a practical algorithm for computing persistence and zigzag persistence for a sequence of general simplicial maps. We leverage the fact that every simplicial map can be simulated by inclusion maps. Therefore, computing the zigzag persistent homology for simplicial map is not more difficult than for inclusion maps. With this new tool, we develop a new algorithm to approximate the persistence diagram of a filtration of Rips complexes induced by inclusion maps.

(This is an ongoing work with Tamal Dey and Yusu Wang at the Ohio State University.)

Title: Zigzag Persistent Homology in Time-Varying Sensor Networks

Abstract:
Methods from applied algebraic topology have been successfully employed to study coverage properties of coordinate-free sensor networks. In this setting, tools from homology are used to compute the presence of `holes' in the coverage area of the network, using only local information from each sensor. Here, we consider a time-varying sensor network observed in at discrete time points, and leverage zigzag persistence to track the homology of this sequence of spaces. This gives a way to distinguish between `persistent' coverage holes due to an underlying problem, and transient holes due to the dynamic nature of the network.

Title: Metrics on Vineyards

Abstract:
Computational topology has become an excellent tool for analyzing static point clouds, but what happens when the point clouds move? With the introduction of vineyards came the analogue to the persistence diagram, but unlike the persistence diagram, there is no obvious notion of distance between two vineyards. In order to compare two dynamic point clouds and their corresponding vineyards, we will look at some options for metrics on vineyards. These metrics arose from looking at point clouds which represent primate group fission and fusion.

Title: Sampling for Local Homology with Vietoris-Rips Complexes

Abstract:
Recently, a multi-scale notion of local homology was proposed by Bendich et. al. to study the local structure of a stratified space around a given point from a point cloud sample. To give reconstruction guarantees, the approach relied on constructing embedded complexes which become difficult to construct in high dimensions. We derive sampling conditions under which the persistence diagrams used for estimating local homology, can be approximated using families of Vietoris-Rips complexes, whose simple construction is robust in any dimension. To the best of our knowledge, our results, for the first time, make stratification learning using local homology feasible in high-dimensions.

(Joint work with Primoz Skraba.)