A hole that lasts across scales

Holes have so far been counted in spaces given exactly: a loop that cannot be pulled tight round the hole of an annulus, a cycle that bounds nothing computed as the kernel of one matrix modulo the image of another, what homology forgets when it replaces loops by cycles. Real data does not come as a space. It comes as a finite set of points — measurements, positions, samples — and a finite set of points has no holes at all. Each point is its own piece and there is nothing between them.

Yet a scatter of points sampled from a ring obviously has a hole, and a scatter sampled from a figure eight has two. The difficulty is saying so in a way that does not depend on a choice the data cannot justify. Join points closer than some distance $r$ and fill in triangles, and the result is a space with honest holes; but the holes depend on $r$, and a different $r$ gives a different answer. Persistent homology, developed around 2000 by Herbert Edelsbrunner, David Letscher and Afra Zomorodian and by Gunnar Carlsson and Afra Zomorodian, refuses to choose. It builds the space at every scale at once and records, for each hole, the range of scales over which it exists.

Joining points at a scale #

The construction is the Vietoris–Rips complex. Fix a scale $r$. Join every two points whose distance is at most $r$ with an edge, and fill in every triangle whose three sides are all edges. The result is a space made of points, segments and triangles, and its holes can be computed exactly: a loop of edges that is not the boundary of a collection of filled triangles is a hole, and the number of independent holes is the first Betti number of the complex.

As $r$ grows, edges and triangles are only ever added, never removed, so the complexes for increasing $r$ are nested, a filtration. A hole appears at the scale where the last edge of its loop is added, and disappears at the scale where enough triangles have been added to fill it. Its persistence is the difference. The barcode on the right of the hero draws each hole as a bar from its birth to its death. For the 44 points round the circle there are two: one from 0.588 to 1.588, the hole in the middle of the ring, and one that lasts 0.025, an accidental gap between neighbouring points that is filled almost as soon as it opens.

No single scale is right #

At a small scale the points have not yet joined into a ring; there are several pieces, and the gaps between them are not holes of the shape. At a large scale, triangles reach across the middle and fill the ring. In between there is a long range of scales where the complex is a ring with exactly one hole. Where that range lies depends on the radius of the circle, the number of points and the noise, none of which the data announces. A method that asked for $r$ in advance would get the circle’s hole only if it guessed well.

The barcode makes the guess unnecessary. The long bar is the range of good scales; its length, a full unit here, is how robust the hole is. Features that last are properties of the shape the points came from. Features that flicker are properties of where the points happened to fall.

Computing the bars #

The bars are found by one matrix reduction. List every point, edge and triangle in order of the scale at which it enters the filtration. Form the boundary matrix over the field of two elements, in which the column of an edge marks its two end points and the column of a triangle its three edges. Then reduce the columns from left to right, adding earlier columns to later ones whenever their lowest marked rows coincide, until every non-zero column has a different lowest row.

After reduction the pairs can be read off. A column that reduces to zero belongs to a simplex that creates something — a new piece, for a point, or a new loop, for an edge. A column whose lowest entry is row $i$ belongs to a simplex that destroys what simplex $i$ created: an edge joining two pieces, or a triangle filling a loop. The bar runs from the scale of the creator to the scale of the destroyer, and creators never paired give bars that run for ever. For 44 points there are 946 edges and 13,244 triangles, every one of which enters the filtration at its own scale.

Read together, the barcodes say: one piece in the end, and one hole that lasts. Those are the Betti numbers of a circle, 1 and 1, recovered from points with no circle in them. The bars of pieces are something familiar in another guise. They are the heights at which single-linkage clustering merges its clusters: each bar ends when its point’s cluster joins a bigger one. Persistent homology in dimension zero is exactly single-linkage clustering, and the dimension-one bars are what clustering never sees.

Why the answer is a list of intervals #

That the output should be a set of bars at all is a theorem, not a convention. At each scale the loops of the complex form a vector space over the field of two elements, and as the scale grows each space maps into the next: a loop at one scale is still a loop, perhaps now a filled one, at every larger scale. A chain of vector spaces and maps like this is a persistence module, and the structure theorem of Zomorodian and Carlsson says that every such module, built from finitely many simplices, splits into a direct sum of pieces each of which is a single copy of the field alive on one interval of scales and zero outside it. Those intervals are the bars, and the splitting is unique up to reordering.

The theorem is the reason the reduction is trustworthy rather than merely convenient. The column additions choose particular cycles to stand for each bar, and different orders of addition choose different cycles, but the intervals they produce never change. It is the same situation as the group a space has at a point, where the loops chosen to represent elements are arbitrary and the group is not. Over the integers rather than a field the splitting can fail, which is one reason almost every computation of persistence works over the field of two elements, where signs disappear and adding a column is the same as removing it.

The theorem also says what persistence cannot record. A bar says that some loop is born at one scale and dies at another; it does not say which loop, and two different families of representing cycles can carry the same barcode. Recovering a good representative — the shortest cycle of the circle sample that lives the whole length of the long bar, say — is a separate and harder problem, and the barcode on its own is silent about it.

Rips, Čech and the union of discs #

The Vietoris–Rips complex is not the only way to join points at a scale. The Čech complex puts down a disc of radius $r$ round every point and fills in a simplex for every set of points whose discs share a common point. By the nerve theorem it has exactly the shape of the union of the discs, which is the object a geometer would reach for first: the union of discs round a sample of a circle is an annulus, and an annulus has one hole. The same union is the one whose pieces minus holes change sign when the discs are scattered at random and the density crosses one.

The Čech complex is expensive, because deciding whether many discs share a point is a geometric computation, while the Rips complex needs only the pairwise distances. The two are sandwiched: the Čech complex of radius $r$ sits inside the Rips complex that joins points at distance $2r$, which sits inside the Čech complex of radius $2r$. So every bar of one appears in the other, stretched by at most a factor of two, and long bars of either are long bars of both. The figures here use Rips because it is cheap; the theorems about the shape of the union are proved for Čech and passed across through the sandwich.

The bars of pieces are a spanning tree #

The dimension-zero bars have a second description that makes them computable without matrices at all. Sort every pair of points by distance and add the edges in that order, keeping an edge only when it joins two different pieces, as in the greedy pass that builds a spanning tree for every graph. The edges kept form the minimum spanning tree of the sample, and the 43 lengths at which they are added are exactly the deaths of the 43 finite bars of pieces. The greedy pass is Kruskal’s algorithm, the reduction of the zero-dimensional columns is the same pass written as linear algebra, and both agree that in the circle sample the last two pieces join at 0.534.

That last join is a quantity worth reading. It is the largest gap that has to be bridged for the sample to become one piece, so it bounds how sparse the sample is along the circle; the loop cannot be born before every gap round the ring is closed, which is why the long bar starts at 0.588, just after it.

Three shapes, three diagrams #

Plotting each bar as a point — birth across, death up — gives a persistence diagram, where long-lived features sit far above the diagonal and short-lived ones close to it. The circle has one point high above the diagonal. The figure eight has two, one for each lobe, so close together that they look like one, because the two lobes are the same size. Points scattered uniformly in a square have none: every loop among them is filled almost as soon as it forms, and all their points hug the diagonal.

So the diagram distinguishes shapes that a quick look at the points might confuse, and it does so with numbers that can be compared, averaged and tested. It has been used to find circular structure in the joint activity of neurons coding head direction, loops and voids in the shapes of proteins, and the large-scale holes in the distribution of galaxies — in each case a shape the points imply but no single choice of scale would reveal.

Small changes, small changes #

The method is useful only if noise cannot create or destroy long bars. The stability theorem of David Cohen-Steiner, Herbert Edelsbrunner and John Harer, from 2007, guarantees it: perturbing the data slightly moves every point of the diagram slightly, with the movement bounded by the size of the perturbation.

The figure checks the bound directly. Each point is moved at random by at most $\delta$ and the bars recomputed; the long bar’s birth and death move by at most 0.0569 even when $\delta = 0.12$, always under $2\delta$. The bound is easy to see for the Rips complex: every birth and death is the length of some edge, and moving each point by at most $\delta$ changes every distance by at most $2\delta$. What the theorem adds is that the matching between the old bars and the new can be chosen so that every bar moves that little, which needs an argument because the bars can change their pairings.

The practical consequence is a rule for reading diagrams: a bar longer than twice the noise in the data cannot be an artefact of the noise. In the circle sample every point lies within 0.15 of the unit circle, and the long bar has length 1.0, more than three times the 0.3 that moving points by 0.15 could account for, so the hole is real; the short bar, 0.025 long, could be erased by moving points by 0.013 and is not evidence of anything.

Pieces and holes at each scale #

Counting the bars alive at each scale gives the Betti numbers of the complex at that scale, the Betti curves. The pieces fall from 44 to 1 as the points join up; a short-lived hole appears briefly; then the count of holes settles at exactly one over the long plateau, and drops to none when the middle fills. The alternating sum of the two curves is the Euler characteristic at each scale, pieces minus holes, which counts targets from overlapping sensors in another use of the same idea.

Topology made quantitative by a scale #

The surprise is that topology, the most qualitative branch of geometry, becomes quantitative the moment scale is allowed to vary. A circle and a figure eight differ in their homology, but a finite sample of either has the homology of a finite set of points, which says nothing. The filtration turns the yes-or-no question “is there a hole?” into the measurable one “for how long is there a hole?”, and the answer is robust where the yes-or-no answer was fragile. The idea is close to the one behind the skeleton that ignores small teeth: a structure computed from a sample becomes trustworthy when it is indexed by a scale, and features are kept or discarded according to how long they persist.

Small samples and two dimensions only #

The samples are small, chosen to make the complexes drawable, and the Rips complex grows like the cube of the number of points; real applications use other complexes and sparsifications to reach millions of points. Only dimensions zero and one are computed. The stability check perturbs one sample seven times and looks only at the longest bar; the theorem covers every bar and every perturbation. And the identification of the long bar with the circle rests on knowing where the points came from; for real data, the method says a hole persists, not what it is a hole in.

Bars reduced here, stability theorem quoted #

Computed here: the Rips filtration of each sample, with every point, edge and triangle ordered by the scale at which it enters; the reduction of the boundary matrix over the field of two elements and the bars read from it, in dimensions 0 and 1; one piece at the end for the circle sample, one loop living longer than 0.7 and the other under 0.3, two long loops for the figure eight and none longer than 0.45 for scattered points; the perturbed samples and the shifts of the long bar, all within $2\delta$; and the Betti curves.

Quoted: the origins of persistent homology in the work of Edelsbrunner, Letscher and Zomorodian and of Carlsson and Zomorodian; the stability theorem of Cohen-Steiner, Edelsbrunner and Harer; the applications to neurons, proteins and galaxies.

Still open: statistics on diagrams #

Persistence diagrams are not numbers or vectors, and doing statistics with them is not straightforward. They can be compared by the bottleneck distance of the stability theorem, but their space under that distance is badly behaved: averages of diagrams need not be unique, and there is no general theory of confidence intervals, hypothesis tests or limit theorems for persistence diagrams comparable to what statistics has for numbers. Partial results exist — for random point clouds the distribution of long bars has been studied, and the expected diagrams of some random complexes are known — and practitioners convert diagrams into vectors, curves or images to use ordinary methods, at the cost of choices the theory does not dictate. A second open question is computational: the Rips complex in high dimension is enormous, and how few simplices suffice to recover the long bars of a large point cloud to a given accuracy is studied but not settled.

The hole that persists #

A finite set of points has no holes, but joined at every scale at once it has holes that are born and die, and the ones that persist over a long range of scales belong to the shape the points were drawn from. Forty-four noisy points round a circle give one loop lasting from 0.588 to 1.588 and an accidental one lasting 0.025; a figure eight gives two long loops and scattered points none; and moving every point by at most $\delta$ moved the long bar by at most 0.057, inside the $2\delta$ the stability theorem guarantees.