Articles

Topology as squinting

One can describe topology, in more descriptive language, as the study of coarse-grained or qualitative features of space. Instead of asking about distances and angles, one asks about connectivity, compactness, the presence of holes (as captured e.g. by homology or more subtly by cohomology), the kinds of paths that live in the space (as captured by the fundamental group), and so on.

Sometimes this loss of precise information is desirable in applications: when we are inundated with data, a more coarse-grained or qualitative perspective can help us see the forest for the trees.

Below we describe two topological tools, both built off homology, which demonstrate this guiding philosophy and how it has turned out to be useful in certain applications.

Persistent homology

Homology is the topological tool of choice in many applications. It contains information about connectedness, compactness, and holes in all dimensions, is conceptually more straightforward than cohomology, and is eminently computable using the tools of linear algebra.

In applications we often start from a point cloud (i.e. a finite set of points) sampled from what we assume to be an underlying manifold. In order to reconstruct the homology of the underlying manifold, we could e.g. the nerve of an open covering constructed by taking balls based at every point in our point cloud, but are immedaitely faced with the question: how big should we make those balls / how fine a covering should we take? Persistent homology offers a compellingly natural answer to this question: use all possible scales, at once.

What is persistent homology?

Persistent homology, as described by one of its originators (Herbert Edelsbrunner), is “an algebraic tool for measuring topological features of shapes and functions [which] casts the multi-scale organization we frequently observe in nature into a mathematical formalism.”

The basic idea is to measure homology “at all possible scales”, and keep track of how homology varies as we pass between these various scales. Below we give more precise formulations of this for Morse functions, and then for triangulable spaces.

Given a Morse function f: \mathbb{R} \to \mathbb{R} (i.e. f is smooth with non-degenerate critical points), we can consider the topology of the sublevelsets, and pair up critical points which cause connected component to be added or removed. A persistence diagram is a diagrammatic representation of this pairing (figure from Edelsbrunner-Harer):

persistd

We can generalize this idea to higher dimensions—for a Morse function f: M \to \mathbb{R} on a n-manifold M = M^n, we obtain n persistence diagrams, one in each degree 0, 1, \dots, n-1 of (nonvanishing) homology.

Alternatively, we may define persistence homology on a simplicial complex (or more generally a triangulable space) K by specifying a filtration \varnothing = K_0 \subset K_1 \subset \dots \subset K_m = K.

The work of Zomorodian and Carlsson, and many others following them, have fleshed out the theory of persistent homology considerably; the Edelsbrunner-Harer survey linked to above is a good starting reference. Some key results:

  • Persistent homology based on homology with k coefficients can be given a k[t]-module structure;
  • Persistent homology is computable in a wide range of settings.
  • Persistence is stable under perturbations (the precise formulation here depends on the setting.)

Applications

One of the first applications of persistent homology was for shape recognition, via a generalization of convex hulls known as alpha shapes. Here we start with a point cloud, and would like to deduce the underlying shape from which (we assume) it was drawn. To do this we start forming alpha shapes—but as above there is a question of which scale we should use in this process. Persistent homology resolves this question by saying that we should take all possible scales, and regard features that “persist” across a (relatively) large(r) range of scales as more likely to be “true” features of the underlying shape.

The idea of persistent homology being potentially useful wherever homology might be useful, but questions of scale exist, can also be seen e.g. in its application to homological criteria for coverage in sensor networks. Given a network of sensors which can communicate with nearby ones, one can “detect” gaps in coverage as non-trivial elements of the second homology of a flag complex with 1-skeleton a sensor communication graph (vertices are sensors, and there is an edge between two vertices if the corresponding sensor ranges overlap.)

The formulation of such a criterion is almost tautological (“there is a hole if the algebra says there is a hole”), but one advantage it has is that second homology can be computed, in a distributed fashion, by the sensors in such a locally-communicating network—while we have not done anything significant conceptually, we have reformulated our intuition in a precise, computable way. To compute it in a robust, noise-proof way which does not require precise knowledge of distance between sensors, however, requires the use of persistent homology (or other tools.)

Topological data analysis

Persistent homology has also been a key tool in topological data analysis, starting with (I believe) the work of Gunnar Carlsson and Afra Zomorodian. The intuition there is that large data sets, while extrinsically huge-dimensional, are often intrinsically low-dimensional in nature, and topology, via persistent homology or other means, provides a good way of effective dimension reduction, because, very roughly speaking, “shape matters”.

The (statistical or other) theory to back this intuition is not always present, although at least on the mathematical side there has been considerable development, driven in large part by possible applications in topological data analysis, to put the theory of persistent homology and its application to data analysis on a sound mathematical footing. Stability theorems, in particular, show that persistent homology at least has a chance of being a sufficiently robust invariant to be useful in data analysis.

There have been a number of applications of these techniques, and indeed a start-up which has made topological data analysis its killer app, although the use of topological techniques in data analysis is still from systematic: successful applications often seem somewhat ad hoc; the generic attempt to apply topological data analysis seems more likely to result in a case of “I found these cycles in my data—but what does that mean?”

Euler calculus

An easier version of homology—or, really, a collapsed or “decategorified” version of it—is the Euler characteristic, and even with part of its topological power collapsed this can still serve useful functions.

For instance, one may notice that the Euler characteristic obeys something that looks like an inclusion-exclusion principle: \chi(A \cup B) = \chi(A) + \chi(B) - \chi(A \cap B). One can formalize this and build a theory of integration “with respect to Euler characteristic” (d\chi) by defining \int_A \chi_A \,d\chi = \chi(A) for characteristic functions of (sufficiently nice) sets, and then extending linearly and using limits.

The sense in which this is like a “squintier” version of Lebesgue integration (say) can be seen clearly in the axiom underlying that definition: instead of associating to the characteristic function \chi_A of a set A the measure of A, we associate to \chi_A the Euler charateristic of A.

The resulting theory is fairly nice—there is a Fubini theorem, Euler integrals can be efficiently computed via the Euler charateristics of level sets and related objects, &c. Not all functions can be integrated, but the ones that tend to be associated with finite point clouds can (a more precise formulation involves o-minimal structures; the functions which can be integrated are those with discrete range and definable preimages according to the o-minimal structure. The theory can be further extended to continuum-valued functions, but that introduces more technicalities, and we do not need it here.) 

Schapira and Oleg first worked the theory out in the late 1980s, and by now it has found applications in tomography, sensor networks, and so on: we briefly describe a few of these below.

An application to tomography

The Schapira inversion formula is a topological version of the inversion formula for the Radon transform. Suppose we have a compact subset T \subset \mathbb{R}^3, and we “scan” T by slicing along hyperplanes and recording the Euler characteristic of the slices of T—which, in the case of a compact set of the plane, is simply the number of connected components minus the number of holes (which equals the number of bounded connected components of the complement—a baby case of Alexander duality.) This yields a function h: \mathrm{AGr}_2(\mathbb{R}^3) \to \mathbb{Z} (the domain here is the affine Grassmannian of all planes in \mathbb{R}^3, not necessarily going through the origin.)

alexdual

Then we can recover the set T (via its characteristic function \chi_T) as follows: encode the information from the “scan” in the relation \mathcal{S} \subset \mathbb{R}^3 \times \mathrm{AGr}_2(\mathbb{R}^3) by (x,\pi) \in \mathcal{S} if x \in \pi \cap T. We may verify h is related to \chi_T by h(\pi) = \int_{\mathbb{R}^3} \chi_T(x) \chi_{\mathcal{S}}(x,\pi) d\chi(x) (a Radon transform, but with d\chi in the place of dx.)

Let  \mathcal{S}_x denote the fiber \{\pi \in \mathrm{AGr}_2 (\mathbb{R}^3) : x \in T \cap \pi\}; then \chi(\mathcal{S}_x) = 1 for all x \in \mathbb{R}^3 (each point in T appears on a compact set of affine planes) and \chi(\mathcal{S}_x \cap \mathcal{S}_y) = 0 for all x \neq y \in \mathbb{R}^3 (given x, y \in T, the affine planes which see both of them are exactly the ones which contain the line containing both of them—and there is a circle’s—or technically a \mathbb{P}^1‘s—worth of such planes.)

The Schapira inversion formula in this case then states that we have \chi_T(x) = \int_{\mathrm{AGr}_2(\mathbb{R}^3)} h(\pi) \chi_{\mathcal{S}}(x,\pi) d\chi(\pi).

Thus in particular it is sufficient to record the connectivity data on the slices to recover the original shape, if one knows enough / has sufficient assumptions on the Euler characteristics of the slices. This seems almost too good to be true—until you realize that actually knowing the Euler characteristic for every slice is still a nontrivial problem. Still, it does give us some latitude to deform which was less present in the original, non-topological Radon transform.

An application to sensor coordination

Baryshnikov and Ghrist have applied Euler integration to the problem of target enumeration via distributed sensor networks. Here the setup is this: we have a bunch of enumeration targets (cats, perhaps, or something less fanciful, such as cars) in a space X covered by a sensor field (in actual applications to be approximated by a sufficiently dense network of sensors.)

Each sensor \alpha records the total number of targets it senses in its range; the sensors can also communicate with nearby sensors (those with overlapping ranges) to exchange and compare target counts, but that is the limit of their capabilities. Given this, and that the sensor ranges overlap in undescribed ways, how should we go about recovering an accurate global count?

Let the target support U_\alpha be the subset of all x \in X s.t. the sensor at x senses \alpha, and h: X \to \mathbb{Z} is the counting function which simply returns the number of targets counted by the sensor at x. In a toy case where X = \mathbb{R}^2—so that we did not have to worry about boundary effects—and all the target supports were perfect circles of radius R, we would have \int_X h \,dx = = \int (\sum_\alpha \chi_{U_\alpha}) = \pi R^2 (\#\alpha), or \#\alpha = \frac{1}{\mu(U_\alpha)} \int_X h\,dx, where here both dx and \mu refer to Lebesgue measure.

Now, if all the target supports U_\alpha have the same nonzero Euler characteristic N (e.g. if they are all contractible, so N = 1), then we can apply exactly the same logic, but using Euler integration instead of Lebesgue integration, to show that the number of \#\alpha = \frac 1N \int_X h \,d\chi.

Hence we did not need our precise geometric hypotheses—that we had no boundary effects, and that all of our target supports were geometrically the same shape; we only needed looser, topological analogues of these hypotheses.

Advertisements
Standard
Snippets, Theorems

Brouwer’s invariance of domain

I am recording here an elementary* result used in the proof of the Teichmueller Existence Theorem.

Theorem (Brouwer). Any injective continuous map from \mathbb{R}^n to itself is open.

*the statement itself sounds elementary enough, but the proof (all known proofs) seem to require some amount of machinery from algebraic topology. Note that one corollary of the theorem is that Euclidean spaces of different dimensions are not homeomorphic, another statement which appears elementary (and intuitive), but is difficult to prove without additional machinery.

It seems that the category of continuous maps contains enough curious things—Peano and other space-filling curves and the like—to quite thoroughly upset our intuitions, although going to the rather more restrictive category of smooth things does restore much of our intuition.

Proof of Theorem: It suffices to show that any such map sends open balls to open balls, or, more narrowly, that for any injective continuous map f: B^n \to \mathbb{R}^nf(0) lies in the interior of f(B^n) (where B^n denotes the closed unit ball.)

Let f be as in the hypothesis of the Theorem. f: B^n \to f(B^n) is a continuous bijection between compact Hausdorff spaces and hence a homeomorphism. f^{-1}: f(B^n) \to B^n is continuous; by the Tietze extension theorem, f^{-1} may be extended to a continuous map G: \mathbb{R}^n \to \mathbb{R}^n.

G has a zero at f(0), and moreover we have the following

Lemma: If \tilde{G}: f(B^n) \to \mathbb{R}^n is a continuous map with \|G - \tilde{G}\|_\infty \leq 1 (i.e. is a small perturbation of G), then \tilde{G} has a zero in f(B^n).

Proof of Lemma: Applying Brouwer’s fixed-point theorem to the function x \mapsto x - \tilde{G}(f(x)) = (G - \tilde{G})(f(x)) (from the closed unit ball to itself) yields a x \in B^n s.t. x = x - \tilde{G}(f(x)), i.e. \tilde{G}(f(x)) = 0.

If f(0) were not an interior point of f(B^n), we may construct a small perturbation of G that no longer has a zero on f(B^n), contradicting the above lemma.

At this point I refer the interested reader to Terry Tao’s blogpost (where the gist of this proof was also taken from; he was interested in Hilbert’s fifth problem, whose solution also makes use of invariance of domain) for the details of the construction.

Corollary Any proper injective continuous map f: \mathbb{R}^n \to \mathbb{R}^n is a homeomorphism.

Proof of Corollary: By invariance of domain, f is open. Now it suffices to show that f is surjective (and hence bijective) for it to be a homeomorphism; but surjectivity follows from f being a proper map into a metrizable space, and hence closed—given E \subset X closed and a sequence of points f(x_n) \in f(E) accumulating to y \in Y and \epsilon > 0, f(x_n) \in B(y,\epsilon) (the closed ball) for all n \geq N = N(\epsilon) \gg 0. By properness, we have, for all n \geq N, x_n \in K \subset E with K compact. Then, up to subsequence, x_n \to x \in K. By continuity, f(x_n) \to f(x) = y, so y = f(x) \in f(E).

Standard
Snippets

Free groups and topology

Any subgroup of a free group is free.

This result is quite interesting, because the statement is purely algebraic yet the simplest proof is topological. Namely, any free group G may be realized as the fundamental group of a graph X. 

The main theorem on covering spaces tells us that every subgroup H of G is the fundamental group of some covering space Y of X; but every such Y is again a graph. Therefore its fundamental group H is free.

Underlined technical details here

Standard