calendar

November 3 (2:30 pm 443 Altgeld) : Harish Chintakunta (UIUC ECE): Topology in Networks and Signal Processing

I will talk about a few applications where topological features play an important role, including emphasis on computational aspects. In sensor networks, I will show how combinatorial Laplacians can be effectively used to find coverage holes and compute persistence of homological features to improve robustness. I will then discuss the relation between restricted Delaunay triangulation and alpha complexes, and its implications in networks.  I think Topology will play a major role in  signal processing and social networks, and we are beginning to see these connections. In signal processing, the entry point for Topology is the delay embedding, where a signal is converted into a point cloud. I will talk about about a simple application of detecting wheezes in breathing signals using this approach, and then share my view of future of topology (and geometry) in signal processing. In social networks, I will present some of our recent findings on how topology influences the core periphery decomposition of a network, and helps in detecting communities. 

April 7 : Ali Belabbas (UIUC ECE): Fundamental limitations in formation control with localized information

Formation control deals with the design of control laws for multi-agent systems in which  agents are required to stabilize at prescribed distances from each other. The most interesting cases, both in theory and practice,  arise when agents only have access to partial information about the state and the objective of the system — we refer to this scenario as formation control with localized information. After formally introducing formation control, we will establish several fundamental limitations stemming from  the information localization: first, we will show that for many formations, local stabilization around prescribed distances requires agents to know the objectives of agents whose states they cannot observe. Second, we will show that information localization can force the appearance of undesired, yet locally stable equilibria. Finally, if time permits, we will show that an often-used gradient-type control law is not robust to mismatch in the objectives.

March 31 : Victoria Blumen (UIUC Math): Singularities of Hinge Structures

I will discuss the paper “Singularities of Hinge Structures” by Ciprian Borcea and Ileana Streinu. This paper studies the singularities of maps associated to the body and hinge structure and panel and hinge structure that is often seen in certain protein chains and other molecular conformations. Several proofs important to robotics research are included and elaborated upon in general dimension.

March 17 : Sayan Mukherjee (Duke Statistics): Random Walks on Simplicial Complexes and Harmonics

In this paper, we introduce random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension d, a random walk with an absorbing state is defined which relates to the spectrum of the k-dimensional Laplacian. We also examine an application of random walks on simplicial complexes to a semi-supervised learning problem. Specifically, we consider a label propagation algorithm on oriented edges, which applies to a generalization of the partially labelled classification problem on graphs.

March 10 : Yuriy Mileyko (Hawaii Math): Duality of Persistence Modules

Topological data analysis (TDA), a new approach to handling high-dimensional data, gained a lot of attention lately. TDA focuses on qualitative rather than quantitative information supported by the data. A central concept in TDA is persistent homology, a topological invariant capturing structural changes in continuous objects reflected by the discrete point clouds. In particular, persistent homology allows one to determine the thresholds where new topological features emerge and where they are later destroyed, providing a so-called birth-death decomposition.

Birth-death decompositions are often represented as collections of planar points called persistence diagrams, and they have been extensively used in a variety of applications. Often, continuous objects associated with a point cloud are sublevel sets of a function on a manifold. In such a case homological duality results may lead to nice relations between persistence diagrams in different homological dimensions, which doesn’t only provide more insight into the theory of persistent homology, but can also be used in practice to reduce computational time. In this talk, I will review some of the existing duality results in persistent homology and show that by focusing not on persistence diagrams but on persistence modules, which are algebraic objects representing birth-death decompositions, one can obtain significantly more general duality results.

February 17 : Omer Bobrowski (Duke Math): Phase Transitions in Random Čech complexes

In manifold learning, one often wishes to infer geometric and topological features of an unknown manifold embedded in a d-dimensional Euclidean space from a finite (random) point cloud. One topological invariant of a considerable interest is the homology of the underlying space.
A common method for recovering the homology of a manifold from a set of random samples is to cover each point with a d-dimensional ball and study the union of these balls. By the Nerve Lemma, this method is equivalent to study the homology of the Čech complex generated from the random point cloud.
In this talk we discuss the limiting behavior of random Čech complexes as the sample size goes to infinity and the radius of the balls goes to zero. We show that the limiting behavior exhibits multiple phase transitions at different levels, depending on the rate at which the radius of the balls goes to zero. We present the different regimes and phase transitions discovered so far, and observe the nicely ordered fashion in which homology groups of different dimensions appear and vanish. One interesting consequence of this analysis is a sufficient condition for the random Čech complex to successfully recover the homology of the original manifold.

February 3 :Chandra Chekuri: Approximation Algorithms for Euler Genus and Related Problems

The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard [Thomassen 1989, 1993], and it is known to be fixed-parameter tractable; that is, for each fixed constant g, there is a polynomial time algorithm that decides whether a given graph G has Euler genus at most g. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(sqrt(n))-approximation is known [Chen, Kanchi, and Kanevsky, 1997] even in bounded degree graphs. In this paper we give a polynomial-time algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus g^O(1) * log^O(1) n. Combined with the upper bound from [Chen, Kanchi, and Kanevsky, 1997], our result also implies a O(n^(1/2 – alpha)-approximation, for some constant alpha>0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPT^O(1) * log^O(1) n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. The talk will focus on the high-level tools for the genus computation coming from the seminal work on graph minors by Robertson and Seymour. Joint work with Anastasios Sidiropoulos.

January 27 :Mark Schubel: Reidemeister Torsion and Combinatorial Vector Fields

We discuss the relationship between Reidemeister torsion and combinatorial vector fields and their flows. We begin by introducing the twisted chain complex and defining Reidemeister torsion and proving some basic properties. We will use this to show that the Reidemeister torsion of a space can be written as the product of the torsion each of the basic sets.

November 19 (1:00 — 3:00 in 141 CSL) :Paul Bendich (Duke): Persistent Homology: Basics, Applications, Software

[This is a tutorial style 2 hour talk and will be in Coordinated Science Lab (CSL) 141]  Topological Data Analysis (TDA) is now around 15 years old, and it is becoming a widely-used technique in data analysis, often in combination with more traditional methods. One of the key tools in TDA is the persistence diagram, which provides a compact description of the multi-scale topological information carried by a point cloud or other embedded object. In this informal tutorial, I will start by going over the very basics of persistent homology, showing how one can go from a point cloud, or a space equipped with a function, and produce a persistence diagram. Depending on audience interest, I can then cover some or all of the following:

-some simple (and not-so-simple) applications which show how persistence diagrams, in combination with statistical ideas, can extract interesting information from unusual datasets.

-the geometry of the space of persistence diagrams: why it’s strange, and the possible implications for statistics with diagrams.

-different algorithms for computing persistence diagrams, some of which are correct and slow, some of which are correct (in certain circumstances) and fast, some of which are fast and approximate with good guarantees.

-a demonstration of our new software package RCA, which gives a very fast (and correct!) computation of persistence diagrams for components and loops.

Please note different (than usual) time, day, and location.

November 18 :Paul Bendich (Duke): Stratifications and Persistent Homology

A stratification of a topological space (with singularities) is a decomposition of the space into manifold pieces, of various dimensions, that all “fit together nicely” in some precisely-defined sense. In this talk, we’ll discuss ways in which algebraic theories about stratified spaces can be combined with persistent homology methods to give insight about actual data. First, we imagine a situation where point cloud data is drawn from or near a stratified space that is embedded in Euclidean space, and our goal is to gain information about the stratification from the point cloud. We give conditions under which this can be done; the main tools are a multi-scale notion of persistent local homology, as well as (co)kernel persistent homology, and the end result is a family of clusterings of the point cloud into groupings which could be placed into the same stratum at different radius scales. Next, we take a different perspective, imagining that we are given a topological space with a fixed stratification endowed with a height function. We show how intersection homology, a homology theory that is particularly sensitive to singularities, can be incorporated into persistent homology theory, giving information about how the height function filters the space and its singularities. Finally, we describe some very recent initial steps towards combining these two theories, illustrating how zig-zag persistent homology can be used to measure changes in the intersection homology of a stratified space, as the stratification itself changes in a continuous fashion.