Distance and persistence diagrams

We assume we have a Morse-type function $f:X\to \R$, whose associated persistence diagram is $D(f) = \{f_1,\dots,f_n\}$, which we will think of as a collection of persistence birth-death pairs $f_i$ in the extended real plane $(\R^*)^2$. If the topological space $X$ was filtered without such a function, define one by $x\mapsto i$ where $i$ is the smallest index such that $x\in X_i$.

Definition: Let $f,g:X\to \R$ be two Morse-type functions with associated persistence diagrams $D(f)$, $D(g)$. The (Wasserstein) $q$-distance between $f$ and $g$ is defined as
\[
W_q(f,g) := \inf_{\sigma\in S_n} \left(\sum_{i=1}^n ||f_i-g_{\sigma(i)}||^q_\infty\right)^{1/q}.\]The bottleneck distance between $f$ and $g$ is
\begin{align*}
W_\infty(f,g) & := \lim_{q\to\infty} \left\{W_q(f,g)\right\} & (\text{limit of $q$-distances}) \\
& = \max_i\left\{||f_i-g_{\sigma(i)}||_\infty\ :\ \sigma = \arg W_q(f,g)\right\}. & (\text{length of longest edge in best matching})
\end{align*}
Example: Consider the torus of inner and outer radius 1 embedded in the natural way. Left $f,g:T^2\to \R$ be height functions of the torus, but projecting to the planes $z=-2$ and $z=x-4$, respectively. Note all critical points occur on the plane $y=0$. Below, the slice at this plane is given (distances along planes from the first critical point are shown), as well as $D(f), D(g)$ on the same diagram (degrees of homology classes are shown).

For $D(f) = \{(0,\infty),(2,\infty),(4,\infty),(6,\infty)\}$ and $D(g) = \{(0,\infty), (2,\infty),(2\sqrt 2,\infty),(2+2\sqrt 2,\infty)\}$, it is clear that $\sigma=\id$ will be the best matching. The $q$-distance between $f$ and $g$ is then given by
\[
W_q(f,g) = \left(||(4,\infty)-(2\sqrt 2,\infty)||^q_\infty+||(6,\infty)-(2+2\sqrt 2,\infty)||^q_\infty\right)^{1/q} = 2^{1/q}(4-2\sqrt 2),\]with bottleneck distance $4-2\sqrt2$. However, we would like to say that these two functions are the same in some way, as no critical points are switched, and extended persistence allows us to do that. The decomposed extended persistence module is given below.

The extended persistence classes have length 3 ($(1,4)$ for the 0-class, $(4,1)$ for the 2-class) and 1 ($(2,3)$ and $(3,2)$ for the 1-classes), no matter if we use $f$ or $g$ to define the $X_i$ and $X^j$.

Remark: An interesting question to ask is how long does it take for an essential homology class to be built? Some things to keep in mind while resolving this question:

• The 0-class case should be treated spearately because of reduced homology
• A class may be encountered several times (like the first 1-class in the example above)
• What does it mean for a class to be "begin being built" (this is probably the key)
• A class is certainly "done being built" (the first time) when it first appears in the persistence module

It seems that the extended persistence pair gives the length between when the class is "done being built" the first time $f$ encounters it fully and when it "begins to be built" the last time $f$ encounters it.

The bottleneck distance satisfies a nice stability condition for tame functions $f:X\to \R$, which have finite dimensional homology groups $H_k(f^{-1}(-\infty,a])$ for all $a\in \R$.

Theorem (Cohen-Steiner, Edelsbrunner, Harer 2007): Let $f,g:X\to \R$ be tame. Then $W_\infty(f,g) \leqslant ||f-g||_\infty$.

This bound is reached when $g=f+c$ for some constant $c$, and the Wasserstein distance is 0 when $g(p_i)=f(p_i)$ for all critical values. Hence it seems without stronger assumptions about $f$ and $g$, this bound is as good as we can get.

References: Edelsbrunner and Morozov (Persistent homology: theory and practice), Cohen-Steiner, Edelsbrunner and Harer (Stability of persistence diagrams)

Revisiting persistent homology

Here we revisit and expand on persistent homology, previously in the post "Persistent homology (an example)," 2016-05-19. All homology, except where noted, will be over a field $k$, and $X$ will be a topological space. Often a Morse-type function $f:X\to \R$ is introduced along with $X$, but we will try to take a more abstract view.

Definition: The space $X$ may be described as a filtered space with a filtration of sublevel sets
\[ \emptyset = X_0 \subseteq X_1\subseteq \cdots \subseteq X_m = X, \] whose persistence module is the (not necessarily exact) sequence
\[ 0 = H(X_0) \to H(X_1)\to\cdots \to H(X_m) = H(X) \] of homology groups of the filtration.

Remark: Every persistence module may be uniquely decomposed as a direct sum of sequences $0\to k\to \cdots\to k\to 0$, where every map is $\id$, except the first and last. The indices at which each sequence in the summand has its first and last non-zero map are called the birth and death of the homology class represented by the sequence.

In some cases a homology class may not die, so we consider the extended persistence module to make everything finite. We introduce the superlevel sets $X^i = X\setminus X_i$. If $f$ was our Morse-type function for $X$, with critical points $p_1<\cdots<p_m$, then for $t_0<p_1<t_1<\cdots<p_m<t_m$, we set $X_i = f^{-1}(-\infty,t_i]$ and $X^i = f^{-1}[t_i,\infty)$. The extended persistence module of $X$ is
\[
0 = H_k(X_0) \to H_k(X_1)\to\cdots \to H_k(X_m) \to H_k(X,X^m) \to H_k(X,X^{m-1}) \to \cdots \to H_k(X,X^0)=0.
\]
Definition: The persistence of a homology class in a persistence module conveys the idea of how long it is alive, presented by a persistence pair.

The persistence of all homology classes in a persistence module is often presented in a persistence diagram, the collection of persistence pairs $(i,j)$, or $(p_i,p_j)$ or $(f(p_i),f(p_j))$, as desired; or a linear barcode, the collection of persistence pairs $(i,j)$ as intervals $[i,j]$, ordered vertically. 

Example: Let $X = T^n=(S^1)^n$ be the $n$-torus. One filtration of $X$ is $X_0=\emptyset$ and $X_i = T^i$ for $1\leqslant i\leqslant n$. Note that $H_k(T^n,T^n\setminus X_n)=H_k(T^n)$ and $H_k(T^n,T^n\setminus X_0)=H_k(\emptyset)$. The first $n+1$ modules of the extended persistence module at level $k$ split into $\binom nk$ sequences, as $H_k(T^n) = \Z^{\binom nk}$. Geometric considerations allow $X^i = T^n\setminus T^i$ to be simplified in some cases. For instance, when $n=3$ and $k=0,1$ we have that $\widetilde H_k(T^3,T^3\setminus T^2)\cong \widetilde H_k(T^3,T^2) \cong \widetilde H_k(T^3/T^2)$, and knowing that $X^1=T^3\setminus T^1\simeq (S^1\vee S^1)\times S^1$, the relevant part of the long exact sequence for relative homology is

The two 1-cycles from $S^1\vee S^1\subset X^1$ map via $f$ to the same 1-cycle in $T^3$, hence $\text{im}(g)=\Z^2$. By exactness, $\text{ker}(g)=\Z^2$, and as $g$ is surjective, $A=\Z$.  Hence the extended persistence $k$-modules decompose as 

The persistence pairs are $(1,3)$ with multiplicity 2 and $(2,3)$, $(3,1)$ with multiplicity 1. The persistence diagrams and barcodes of the degree 0 and 1 homology classes are given below.

The diagonal $y=x$ is often given to indicate how short a lifespan a class has. Barcodes are usually not given for extended persistence diagrams, as length of a class (birth to death) is less important than position (above or below the diagonal).

Now we consider some generalizations of the ideas presented above.

Remark: A filtration can also be viewed as a diagram $X_0 \to X_1 \to \cdots \to X_m$, where each arrow is the inclusion map. We could generalize and consider a zigzag diagram, a sequence $X_0 \leftrightarrow X_1 \leftrightarrow \cdots \leftrightarrow X_m$, where $\leftrightarrow$ represents either $\to$ or $\leftarrow$. Homology can be applied and the resulting seuquence can also be uniquely decomposed into summands $k \leftrightarrow \cdots \leftrightarrow k$ where every arrow is the identity, giving zigzag persistent homology.

Remark: A filtration could also be viewed as a functor $F:\{0,\dots,m\}\to \text{Top}$, where $F(i)=X_i$ and $F(i\to j)$, for $j\>i$, is the composition of maps $X_i\to \cdots \to X_j$. Hence the degree-$k$ persistent homology of $X_i$ can be defined as the image of the maps $H_kF(i\to j)$, for all $j\>i$, and the functor $H_kF:\{0,\dots,m\}\to \text{Vec}$ may be viewed as the $k$th persistence module. This is a categorification of persistent homology.

Remark: A space $X$ can be filtered in several different ways. A multifiltration $X_\alpha$, for $\alpha$ a multi-index, is a collection of filtrations such that fixing all but one of the indices in $\alpha$ gives a (one-dimensional) filtration of $X$. The multidimensional persistence of $X_\alpha$ is a $|\alpha|$-dimensional grid of homology groups, with the barcode generalizing to the rank invariant, a map on the grid.

Another generalization, viewing filtrations as quivers, will not be discussed here, but rather presented as a separate post later.

References: Edelsbrunner and Morozov (Persistent homology: theory and practice), Carlsson, de Silva, and Morozov (Zigzag persistent homology and real-valued functions), Bubenik and Scott (Categorification of persistent homology), Carlsson and Zomorodian (The theory of multidimensional persistence)