Topological Simplification Guided by Forbidden Regions

Simplification of real-valued functions is one of the central topics in Morse theory. In the classical (smooth) setting, one of the most notable examples of such simplifications is performed throughout the proof of the h-cobordism theorem [25, 24]. In the discrete setting, Forman’s theory [18, 17] studies the reversal of a unique combinatorial path between two critical points as a way of reducing the total number of critical points and, therefore, simplifying the Morse complex.

More recently, simplification has been studied in the context of persistent homology. The authors of [14] introduced the problem of persistence-sensitive simplification – asking to simplify all pairs with persistence below a given threshold – and gave an algorithm for 2-manifolds. Their solution was later improved to linear time [1]. Another approach, based on Forman’s combinatorial vector fields, was presented in [3]. This work drew connection to the cancellation procedure by observing that whenever the unique path connects two critical points with locally lowest difference in function values, their cancellation does not affect the remaining part of the persistence diagram [3]. These apparent pairs have also been called close pairs [9] and shallow pairs [15].

This observation further helped in optimization of (persistent) homology computation [2] and shape reconstruction [4]. The idea of pruning pairs of critical cells, following Forman’s approach, has been extensively studied in data visualization [6, 7, 10, 16, 21, 22, 27]. Recent works on topological optimization [20, 26] offer an alternative, albeit less controlled approach to simplification.

But there remains a critical gap. The works that are able to rigorously control the changes in persistent homology [14, 1, 3] are only able to simplify 0-dimensional persistent homology (as well as codimension-1, by duality). Meanwhile, the middle dimensions – e.g., 1-dimensional homology on 3-manifolds – are important in practice.

In this work, we study how relations between persistence pairs calculated by the standard lazy reduction algorithm [11, 5] can guide us in simplifying a discrete Morse function $h$, while controlling the changes in its persistence diagram in any dimension and the overall gradient structure. These relations organize persistence pairs in a hierarchical structure called a depth poset [12]. As observed in [13, 26], these relations describe the obstacles to modifying a function without changing its persistence diagram.

Concretely, for a given persistence pair $\alpha$, we define forbidden regions for its death and birth cells, which describe the parts of the persistence diagram that $\alpha$ cannot move to without changing the persistence pairing. Conversely, when the forbidden regions leave a gap – a path from $\alpha$ to the diagonal – we can construct a homotopy that brings $\alpha$ to the diagonal without changing the rest of the persistence pairs and the gradient structure. This allows us to identify a broader family of persistence pairs, possibly with high persistence, that can be safely and selectively removed. We summarize our main contribution in the following theorem, where $\mathrm{BD}(h)$ denotes the set of birth-death pairs induced by a discrete Morse function $h$, and $\mathrm{Crit}({𝒱}_h)$, the set of critical cells for $h$.

We present a constructive proof to this theorem, which provides an algorithm explicitly tracking all changes in relations throughout the homotopy and the final path reversal. As a result, we obtain already computed relations between pairs in $\mathrm{BD}(h^{\prime })$, which enables iterative simplification.

Lefschetz complexes generalize simplicial, cubical, and cellular complexes while remaining concrete enough to define persistent homology. When it does not lead to confusion, we shorten the notation and refer to the set of cells, $X$, as the Lefschetz complex. We often interpret $D$ and $D^{⟂}$ as a matrix, in which case we put the arguments in the square brackets for emphasis, e.g., $D[x,y]$. We write $X_n$ for the set of $n$-dimensional cells of $X$, and $D_n$, $D_n^{⟂}$ for the $n$-th boundary and coboundary matrix, respectively.

In particular, we say that $X$ is filtered by $h$. It also induces an $h$-order on $X$:

If $X$ is filtered by a dMf $h$, then we always assume that rows and columns of $D_n$ are ordered by the $h$-order, and those of $D_n^{⟂}$ by the reversed $h$-order.

To calculate persistent homology, we use the original version of the persistence algorithm [11], called lazy reduction algorithm, described in the form we need in [26]. The algorithm relies on an auxiliary function $\mathrm{low}$, which, for a given column, returns the index of the row containing the lowest non-zero entry in that column. For a given (co)boundary matrix $D_n$, Algorithm 1 performs successive column additions, which results in a decomposition $D_n=R_n{U}_n$ with $U_n$ invertible and upper triangular. Moreover, if $x\ne y$ and $U_n[x,y]\ne 0$, then column $R_n[:,x]$ was added to $R_n[:,y]$ by the algorithm. Observe that in $D_n$ the rows are indexed by $(n-1)$-dimensional cells and the columns by $n$-dimensional cells. The same holds for $R_n$; however, both the rows and columns of $U_n$ are indexed by $n$-dimensional cells. Similarly, we obtain $D^{⟂}=R^{⟂}{U}^{⟂}$ decomposition by applying $D^{⟂}$ to the algorithm.

We say that $\alpha =({\alpha }^{\circ },{\alpha }^{\times })$ is an ($n$-dimensional) birth-death pair if ${\alpha }^{\circ }$ is a low of $R_{n+1}[:,{\alpha }^{\times }]$. $\alpha$ is an ($n$-dimensional) birth-death pair if and only if ${\alpha }^{\times }$ is a low of $R_n^{⟂}[:,{\alpha }^{\circ }]$ [8]. We refer to ${\alpha }^{\circ }$ and ${\alpha }^{\times }$ as birth and death cells, respectively. The dimension of a birth-death pair is the dimension of its birth cell. We denote the set of all birth-death pairs by $\mathrm{BD}(h)$ and the set of all $n$-dimensional birth-death pairs by ${\mathrm{BD}}_n(h)$. The cells in dimension $n$ that are not paired at all – their columns in $R_n$ are zero, and there are no columns in $R_{n+1}$ that have them as the lowest non-zero entry – are $n$-dimensional homology generators. It is convenient to assume that these generators also belong to some birth-death pair, even if its second component is undefined.

Let $x,y\in X_n$. If $U_n[x,y]=1$, we say that there is a homological relation between $x$ and $y$ and denote this fact by $x\stackrel{\times }{\to }y$. Dually, if $U_n^{⟂}[x,y]=1$, we write $x\stackrel{\circ }{\to }y$ to indicate a cohomological relation. If the relation type is not important, we simply write $x\to y$. If $x$ and $y$ are unrelated, we write $x\nrightarrow y$, adding a superscript to specify the missing relation type, e.g., $x\mathrm{／}\stackrel{\times }{\to }y$ if $U[x,y]=0$. Observe that if $x\stackrel{\times }{\to }y$, then $x$ must be a death cell, whereas $y$ may be either a death cell or birth cell. Similarly if $x\stackrel{\circ }{\to }y$ then $x$ has to be a birth cell, while the type of $y$ remains unspecified. We extend these notions to birth-death pairs: $\beta \stackrel{\times }{\to }\alpha$ whenever ${\beta }^{\times }$ is homologically related to any component of $\alpha$; similarly for other kinds of arrows. As rows and columns of $D_n$ and $D_n^{⟂}$ are ordered with respect to the $h$-order and the reversed $h$-order, so are $R_n$, $R_n^{⟂}$, $U_n$ and $U_n^{⟂}$. We emphasize that $R_n^{⟂}$ and $U_n^{⟂}$ are not transposed matrices $R_n$ and $U_n$, but components of lazy decomposition $D_n^{⟂}=R_n^{⟂}{U}_n^{⟂}$.

The persistence diagram is a set of two dimensional points $(h({\alpha }^{\circ }),h({\alpha }^{\times }))$ for $\alpha \in \mathrm{BD}(h)$. When we visualize a persistence diagram (see Figure 2), it is convenient to add the diagonal, i.e., all points $(x,x)$ for $x\in ℝ$, and to annotate the arrows with the type of the relation. Since a dMf is not injective in general, it can generate birth-death pairs on the diagonal of the persistence diagram. We denote the set of such diagonal pairs by $\overline{\mathrm{BD}}(h)$ and use notation $\widehat{\mathrm{BD}}(h)$ for the pairs above the diagonal.

The preceding observation means that if we depict every relation between the birth-death pairs of the same dimension as arrows in the persistence diagram, then every such arrow points up and to the left.

In words, a topological simplification removes some off-diagonal persistence pairs and preserves the rest.

A combinatorial vector field $𝒱$ induces a digraph $G_{𝒱}=(X,E)$. Every edge $(x,y)\in E$ is either an explicit arc when $(x,y)\in 𝒱$ or an implicit arc when $D(y,x)=1$ and $(x,y)\notin 𝒱$. A path $\rho$ has dimension $k$ if it consists only of cells of dimension $k$ and $k+1$. In particular, any path from $y$ to $x$, where $x,y\in \mathrm{Crit}(𝒱)$ and $k=dim(x)=dim(y)-1$ is of dimension $k$ and alternates between $k$ and $k+1$ dimensional cells.

A combinatorial vector field $𝒱$ is called gradient if $G_{𝒱}$ is acyclic. If there is a path between vertices $y$ and $x$, then we write $y\stackrel{𝒱}{\rightsquigarrow }x$, omitting the superscript when the vector field is clear from the context. ${𝒱}^k$ denotes the union of all $k$-dimensional vectors and critical cells of dimension $k$ and $k+1$. Finally, note that for a given discrete Morse function $h$, the non-empty preimages ${𝒱}_h≔\{h^{-1}(a)\mid a\in ℝ,h^{-1}(a)\ne \mathrm{\varnothing }\}$ form a combinatorial gradient vector field.

The Morse complex connects homological and dynamical perspectives on scalar functions. It is not required to carry out the reasoning we need, but it will simplify it considerably.

The most useful properties of Morse complexes for our work is that they describe the off-diagonal birth-death pairs. Indeed, if ${𝒱}_h$ is a gradient vector field of some dMf $h$, its restriction to $ℳ({𝒱}_h)$, denoted by $h_{ℳ}$, is an injective dMf. The next observation follows from [15, Theorem 4.3].

It follows that we can identify the components of the pairs in $\widehat{\mathrm{BD}}(h)$ with elements of $\mathrm{Crit}({𝒱}_h)$, while the vectors are the diagonal pairs, $\mathrm{Vec}({𝒱}_h)=\overline{\mathrm{BD}}(h)$. This perspective enables us to apply the following classical theorem.

We say that $\alpha \in \widehat{\mathrm{BD}}(h)$ is reversible if there exists exactly one path between ${\alpha }^{\times }$ and ${\alpha }^{\circ }$ in ${𝒱}_h$. However, the theorem alone gives no guarantee that elimination of a pair of critical cells will not affect the remaining pairs in $\widehat{\mathrm{BD}}(h)$. Identifying those pairs that can be safely removed is therefore a key challenge.

Observe that every shallow pair is a birth-death pair. Shallow pairs were introduced as apparent pairs in [2] and as close pairs in [9]. Since the theory behind them was later developed in the framework of the depth posets [13], we adopt the name from that setting. Shallow pairs are closely related to an algebraic operation called Lefschetz cancelation.

The boundary map in the quotient can be written in matrix form: if $dimt=n$ and ${\widehat{D}}_n$ is the $n$-th boundary matrix of $\widehat{X}$, then ${\widehat{D}}_n[:,y]=D_n[:,y]+D_n[s,y]\cdot D_n[:,t]$, after erasing row $s$ and column $t$. Throughout this paper, we often refer to small modifications of matrices based on their previous state. In such cases, any matrix $M$ after modification is denoted $\widehat{M}$.

In other words, performing a Lefschetz cancellation on a shallow pair does not change the pairing between the rest of the cells. It is convenient to characterize shallow pairs in terms of the relations between cells.

It is important to note that a Lefschetz cancellation leaves intact not only the pairing, but also the relations between cells.

The above theorem can be rephrased as follows.

Due to Observation 2 above, we introduce critical shallow pairs. An off-diagonal birth-death pair $\alpha$ is a critical shallow pair if there does not exist an off-diagonal birth-death pair $\beta$ such that $\beta \to \alpha$. It is easy to see that critical shallow pairs are exactly the shallow pairs of the Morse complex, although they need not be shallow pairs in the original complex. Equivalently, a pair $\alpha$ is critically shallow if for every $\beta \to \alpha$, the pair $\beta$ is a vector in ${𝒱}_h$.

So to find a topological simplification of $h$, one can find a critical shallow pair $\alpha$ that is reversible. Then, one has to invert the unique path $\rho$ between ${\alpha }^{\times }$ and ${\alpha }^{\circ }$, and find $h^{\prime }$ with the property that ${𝒱}^{-\rho }={𝒱}_{h^{\prime }}$ and $h_{|\mathrm{Crit}({𝒱}^{-\rho })}=h_{|\mathrm{Crit}({𝒱}^{-\rho })}^{\prime }$. Unfortunately, it may happen that there is no pair that is both shallow and reversible. One of the goals of this paper is to remedy this problem.

To understand how birth-death pairs and the relationships between them change during changes of the dMf, one must study how they change upon transposition of two adjacent cells in the boundary matrix. This problem is well-studied; see [5] and [13]. Observing that the depth poset can be constructed from the union of homological and cohomological relations between birth-death pairs (see Theorem 4.8 in [12]), we reformulate the results from [13] in the language of this paper. First, we introduce two additional objects.

Lemma 3 proves that the following definition is unambiguous.

Note that in the above definition, we can cancel all pairs in the bottom-right quadrants because, from Observation 2, there is no $\gamma \in {\mathrm{BD}}_n(h)$ such that $\beta \to \gamma \to \alpha$. After the cancellations, we have either (i) both $\alpha$ and $\beta$ are shallow, or (ii) $\beta \to \alpha$ and $\beta$ is shallow, or (iii) $\alpha \to \beta$ and $\alpha$ is shallow.

Now we are ready to utilize results from [13] in a series of theorems.

Figure 2 presents an example of how a transposition affects the relationship between birth-death pairs. Now we introduce our own propositions, which will be useful later.

Note that a transposition may involve skipping two columns and rows when bypassing a combinatorial vector. The following proposition helps decrease complexity of the final algorithm.