Apex Representatives

Given a filtered cell complex $K$, let $D$ be a matrix that represents its boundary operator, with rows and columns ordered according to the filtration. To find ordinary persistence pairing, one can compute a decomposition, $R=DV$, where matrix $R$ is reduced, meaning its pivots – lowest non-zero elements in its columns – appear in unique rows, and matrix $V$ is full-rank upper-triangular. We index the columns and rows of the matrices by the (totally ordered) cells of the input complex. The persistence pairing is given by the pivots of matrix $R$: a $p$-dimensional homology class created by the addition of simplex $\sigma$ is destroyed by the addition of simplex $\tau$ iff $\mathrm{low}R[\tau ]=\sigma$, where $\mathrm{low}R[\tau ]$ returns the pivot in the column $R[\tau ]$. By definition, the corresponding column $V[\tau ]$ stores a $(p+1)$-dimensional chain whose boundary is the cycle $R[\tau ]$.

The decomposition $R=DV$ is not unique: multiple matrices $R$ and $V$ satisfy it. However, the original persistence algorithm [10] performs operations in a lazy fashion, subtracting columns from left to right only if their pivots collide. We call this a lazy reduction. It has the following special properties that simplify our algorithms.

Induction on $V$; see [17]. $◀$

The contrapositive of the lemma is the following corollary.

We start with a zigzag of simplicial complexes,

where every consecutive pair of complexes vary by at most one simplex, i.e., $K_i$ can be equal to $K_{i+1}$ in the sequence. It is convenient to assume that every simplex $\sigma$ appears and disappears exactly once in this sequence, and therefore is present during some interval $T(\sigma )=[i,j]$, i.e., $\sigma \in K_k$ iff $k\in T(\sigma )$. This assumption can be made without loss of generality by assuming that the union $K$ of all simplices across all times, $K={\bigcup }_i{K}_i$ forms a $\mathrm{\Delta }$-complex. The full definition of this object is too verbose – we refer the reader to [7], which adapts the classical concept of $\mathrm{\Delta }$-complexes in [14, p. 103] to our case of zigzag filtration – but informally it relaxes the requirement that in a simplicial complex two simplices intersect in a common face. All the familiar notions of simplicial homology work the same, but now instead of having a simplex supported over multiple intervals in the zigzag, we can have multiple simplices, with the same boundary, each supported on a single interval. We use $m=|K|$ to denote the size of the input complex.

Applying homology, we get a zigzag of homology groups, where we suppress dimension for simplicity,

Just like with ordinary persistence, this zigzag decomposes into $k$ bars or persistence intervals [3]. Let $\{{\alpha }_i^1,\mathrm{\dots },{\alpha }_i^k\}$ be a choice of elements in $𝖧(K_i)$ such that the non-zero elements form a basis for $𝖧(K_i)$. We say that such bases are compatible across the zigzag if the maps in Equation 2 diagonalize, i.e., ${\alpha }_{2i-1}^j↤{\alpha }_{2i}^j\mapsto {\alpha }_{2i+1}^j$. For every $j$, ${\alpha }_{\ast }^j$ are non-zero over a single persistence interval $[b^j,d^j]$. Cycles $z_i^j$ that give a set of compatible bases ${\alpha }_i^j=[z_i^j]$ are called zigzag representatives, with $z_{\ast }^j$ being the representatives of the $j$-th bar in the zigzag barcode.

A convenient setting for persistence is that of a Morse-like [4] real-valued function $f:𝕏\to ℝ$. We denote with ${𝕏}_a^b=f^{-1}[a,b]$ the preimage of an interval and allow the endpoints to be infinite, $a,b=\pm \mathrm{\infty }$, in which case the interval is understood to be open at the infinite ends. We denote the following pairs of spaces:

Let be the critical values of the function $f$. Let $s_i$ be regular values interleaved with the critical values: . The following constructions play an important role in the theory of persistent homology:

• $\mathrm{■}$

  Extended persistence (EP):

  	$0$	$\to 𝖧(𝕏[-\mathrm{\infty },s_0])\to \mathrm{\dots }\to 𝖧(𝕏[-\mathrm{\infty },s_n])=𝖧(𝕏)$
  		$\to 𝖧(𝕏[-\mathrm{\infty },s_n))\to \mathrm{\dots }\to 𝖧(𝕏[-\mathrm{\infty },s_1))\to 𝖧(𝕏[-\mathrm{\infty },s_0))=0.$

• $\mathrm{■}$

  Levelset zigzag (LZZ):

  $$0\leftarrow 𝖧\left(𝕏[s_0,s_0]\right)\to 𝖧\left(𝕏[s_0,s_1]\right)\leftarrow 𝖧\left(𝕏[s_1,s_1]\right)\to \mathrm{\dots }\to 𝖧\left(𝕏[s_{n-1},s_n]\right)\leftarrow 𝖧\left(𝕏[s_n,s_n]\right)\to 0.$$

Carlsson et al. [5] showed that these two sequences contain the same information by arranging the four types of spaces into a Mayer–Vietoris Pyramid, see Figure 2(left). Once homology is applied, the pyramid unrolls into an infinite Mayer–Vietoris strip of homology groups, where every diamond belongs to the Mayer–Vietoris long exact sequence, making it exact in the terminology of [3], see Figure 2(right). This allows one to translate the decomposition between any two paths that differ by a single diamond (and therefore between any pair of paths via composition).

Bendich et al. [2] further showed that the translation rules in [5] hold at the level of the basis elements of the individual paths, which means the entire pyramid decomposes as a direct sum of (indecomposable) pointwise $1$-dimensional diamond summands, flush with its boundaries, shown in blue in Figure 2(right). The decomposition of the levelset zigzag and extended persistence are simply slices through these flush diamond summands. Bauer et al. [1] study the Mayer–Vietoris Pyramid in the cohomological setting.

We call the bottom-most space in the support of a diamond its apex. The homology class assigned to the diamond in that space, an apex class, and any cycle that belongs to such a class, an apex representative. We note that just like the choice of the basis for ordinary persistence is not unique, neither is the choice of the apex classes. An apex class is characterized by lying outside the image of the maps into the apex; specifically, for the four types of apexes their classes satisfy:

Because there is a map from the apex to every space in the diamond, we can recover a representative in any space by simply mapping an apex representative forward. All the maps in the pyramid are inclusions, except for the boundary homomorphism connecting two consecutive dimensions of homology in the strip. We say more about this translation in Section 7, but the overarching point is that given an apex representative, it is straightforward to recover every other representative, and levelset zigzag representatives in particular.

Given a zigzag in Equation 1, we define a larger cell complex $\overline{K}$, called a prism:

together with a function $\overline{f}:|\overline{K}|\to ℝ$ on its underlying space, defined by the projection onto the second component, $\overline{f}(x\times t)=t$. See Figure 3. We observe that the prism consists of two types of cells: horizontal cells $\sigma \times [i,i+1]$ and vertical cells $\sigma \times i$.

We define an integer interlevel set, for $i,j\in \mathbb{Z}$, ${\overline{K}}_i^j=\{\sigma \times T\in \overline{K}\mid T\subseteq [i,j]\}.$ We note that its underlying space $|{\overline{K}}_i^j|={\overline{f}}^{-1}[i,j]$. Then for any pair of integers $b,d$, we get four types of pairs of subspaces,

Applying homology to each pair, we get relative homology groups that appear in the four quadrants of the Mayer–Vietoris pyramid: $𝖧(\overline{K}[b,d]),𝖧(\overline{K}(b,d])),𝖧(\overline{K}[b,d)),𝖧(\overline{K}(b,d))$.

Because even-indexed spaces in Equation 1 include into odd-indexed spaces, $K_{2i-1}\leftarrow K_{2i}\to K_{2i+1}$, we have an isomorophism of homology groups $𝖧(\overline{K}[2i,2i+1])\simeq 𝖧(\overline{K}[2i+1,2i+1])\simeq 𝖧(\overline{K}[2i+1,2i+2])$, induced by deformation retractions. It follows that the levelset zigzag [5] of function $\overline{f}$,

is isomorphic to our starting zigzag in Equation 2. Explicitly, the isomorphism is given by the following bijection between the four types of intervals:

Because we perform computation on the input complex $K$, rather than the prism, we need a notation for different intervals and pairs of intervals. The connection between these and the corresponding intervals in $\overline{K}$ will be made clear in Section 6. We denote the sub- and super-level sets:

and define four pairs of spaces:

Because every step of the input zigzag is a simplicial complex, it follows that for any $\sigma ,\tau \in K$,

The following relationships between sub- and super-levelsets follow immediately:

To compute the persistence decomposition of the zigzag, we follow the algorithm of Dey and Hou [7], who use a construction similar to extended persistence [6] on the cone $\widehat{K}=\omega \ast K$ over the input complex $K$, where $\ast$ indicates a join with the cone vertex $\omega$. Every simplex $\sigma$ in the base space $K$ gets value $\min (\sigma )$ from the input zigzag. Every simplex $\widehat{\sigma }$ in the cone $\widehat{K}-K$ gets value $\max (\sigma )$ from the input zigzag. We then define a filtration, where the base space simplices come first, ordered by increasing value, and the cone simplices come second, ordered by decreasing value. Specifically,

which in reduced homology is isomorphic to

The latter is an ordinary filtration and we compute its persistence via the $R=DV$ decomposition of the boundary map of the cone $\widehat{K}$. Crucially, the resulting bars are in one-to-one correspondence with the bars in the decomposition of the input zigzag in Equation 2.

The correctness of Algorithm 1 follows from the following claim about the boundary structure, which will be important in Section 6. We let $z_x^y$ be the restriction of cycle $z$ to the simplices $\tau$ whose times $t_{\tau }$ lie in the interval $[x,y]$, i.e., $z_x^y={\sum }_{\tau \in z,t_{\tau }\in [x,y]}⟨\tau ,z⟩\cdot \tau$.

Simplex $\sigma$ generates a cell $\sigma \times [s,l]\in \overline{z}$ iff $⟨\sigma ,w_{\text{init}}⟩\ne 0$ (Line 5). This cell contributes $\sigma \times s$ to the boundary of $\overline{z}$. Simplex $\sigma$ generates a cell $\sigma \times [l^{\prime },f]\in \overline{z}$ iff $⟨\sigma ,w_{\text{init}}⟩+{\sum }_{\tau \in \delta \sigma \cap z_b^d}⟨\sigma ,\tau ⟩\ne 0$. By definition this is the case only for simplices in $w_{\text{final}}=w_{\text{init}}+\partial z_b^d$. $\mathrm{⊲}$ It follows that if $w_{\text{init}}\subseteq K[s,s]$, then $\overline{z}$ is a cycle in $\overline{K}I$. What is not immediate is why the chains $\sigma \times [l,t_{\tau }]$ and $\sigma \times [l,f]$ in Lines 9 and 13 are in the prism $\overline{K}$.

Without loss of generality, assume . There are three types of chains:

1. 1.

   $\sigma \times [s,t_{{\tau }_1}]$. $\sigma$ has a non-zero coefficient on this interval iff $⟨\sigma ,w_{\text{init}}⟩\ne 0$ (Line 5), in which case $\sigma \in K[s,s]$. Existence of coface ${\tau }_1$ implies .

2. 2.

   $\sigma \times [t_{{\tau }_i},t_{{\tau }_{i+1}}]$. From Equation 4, .

3. 3.

   $\sigma \times [t_{{\tau }_i},f]$. Suppose that this chain is not in $\overline{K}$. This means $x=\max (\sigma )\in [t_{{\tau }_i},f)$. Equation 4 implies that $\sigma$ has no cofaces in $[x,f]$. Therefore, $\sigma \in w_{\text{init}}+\partial z_s^x$ and $\sigma \notin \partial z_x^f$. Therefore, $\sigma \in \partial z$. Since we assumed $z$ is a relative cycle in $KI$, it cannot have any boundary inside the interval itself – a contradiction.

$\mathrm{⊲}$

Let $m$ be the size of the input $p$-cycle $z$. Algorithm 1 requires $O(p\cdot m\log m)$ time. It goes through all simplices $\sigma$ that are faces of some simplex $\tau \in z$; there are at most $(p+1)\cdot m$ such $(p-1)$-simplices. For each one, the algorithm sorts its cofaces by their times $t_{\tau }$. Although there is no bound on the number of cofaces of one simplex, the total number of the cofaces to sort is again at most $(p+1)\cdot m$. Individual operations in the update take constant time, so the overall running time of Algorithm 1 is $O(p\cdot m\log m)$. The size of the lifted cycle is $O(p\cdot m)$.

All the statements follow the same proof, except for the endpoints of the intervals, so we only show the first. Suppose there is some class $[\alpha ]\in 𝖧(\overline{K}(b,d-1])$ that maps to $[\overline{z}]\in 𝖧(\overline{K}(b,d])$. Then $\overline{z}=\alpha +\partial \beta$ for some chain $\beta$. Since $\tau \in \overline{z}$ and $\tau \notin \alpha$ (since $\min \tau =d>d-1$), $\tau$ must be in $\partial \beta$. But from Equation 4, $\tau$ has no cofaces in $K_{-1}^d$ – a contradiction. $◀$

All the statements follow the same proof, except for the endpoints of the intervals, so we only show the first. From the long exact sequence of the triple [14, p. 118], $K_{-1}^{b-1}\subseteq K_{-1}^b\subseteq K_{-1}^d$, we know that the image in the claim is equal to the kernel of the map induced by the boundary,

For $[\overline{z}]$ to be in the kernel, $\partial \overline{z}$ needs to be a relative boundary in $\overline{K}(b-1,b]$, i.e., $\partial \overline{z}=\partial \beta +\gamma$ for some $\beta \subseteq K_{-1}^b$ and $\gamma \subseteq K_{-1}^{b-1}$. Since $\sigma \in \partial \overline{z}$ and $\sigma \notin \gamma$, $\sigma$ must be in $\partial \beta$. But from Equation 4, $\sigma$ has no cofaces in $K_{-1}^b$ – a contradiction. $◀$

Putting Lemmas 7 and 8 together, we get the following theorem.

The main content of this section is summarized in Table 1: lifting the stated cycles $z$ in $K$, derived from the lazy reduction, with the given arguments to the algorithm Lift-Cycle, produces apex representatives in $\overline{K}$. The results of the section are more general, but also more verbose; they derive the expression for the cycles for any reduction.