Super-Polynomial Growth of the Generalized Persistence Diagram

Persistent homology is a central concept in Topological Data Analysis (TDA), which is useful for studying the multi-scale topological features of datasets [16, 17, 27]. In the classical one-parameter setting, topological features in datasets are summarized in the form of persistence diagrams or barcodes [23, 65], which serve as complete, discrete invariants of the associated persistence modules.

Multi-parameter persistent homology generalizes persistent homology. In the $d$-parameter setting, topological features of datasets are indexed by the poset ${ℝ}^d$ or a subposet of ${ℝ}^d$ [11, 18]. This generalization allows for a finer extraction of topological features, enabling a more detailed analysis of complex datasets [19, 24, 46, 47, 59, 63, 64]. However, the algebraic structure of multi-parameter persistence modules, i.e. functors from the poset ${ℝ}^d$ ($d\ge 2$) to the category ${\mathrm{𝐯𝐞𝐜}}_{𝔽}$ of finite dimensional vector spaces over a field $𝔽$, is significantly more complex, and in fact no complete discrete invariant exists for multi-parameter persistence modules [18].

Many incomplete, but potentially useful invariants for multi-parameter persistence modules have been studied; e.g. [3, 4, 8, 12, 21, 34, 35, 44, 45, 51, 54, 58]. The Generalized Persistence Diagram (GPD) is one such invariant and is a natural extension of the persistence diagram for one-parameter persistence [39, 55]. The GPD is defined as the Möbius inversion of the Generalized Rank Invariant (GRI)¹¹1The term “generalized persistence diagram” sometimes refers to different concepts; e.g. [14, 52, 56]. Also, we note that the notion of the GRI stems from the concept of the rank invariant [18]. , which captures “persistence” in multi-parameter persistence modules or, more generally, any linear representations of posets [40]. Many aspects of the GPD and GRI–such as stability, discriminating power, computation, connections to other invariants, and generalizations–have been studied; e.g. [5, 12, 22, 25, 26, 31, 41, 42]. Also, a vectorization method for the (restricted) GRI has recently been proposed and utilized in a machine learning context [53, 64]. There are also other works on invariants of multi-parameter persistence modules that are closely related to the GPD and GRI; e.g. [3, 4, 5, 8, 15, 34, 36].

While many properties of the GPD have been clarified in the aforementioned works, computing the GPD, unlike its classical counterpart, remains a significant challenge. The main hurdle is that, while the GPD is defined as the Möbius inversion of the GRI, computing the GRI is intractable mainly due to the formidable size of its domain. For instance, the domain of the GRI of a persistence module over a finite grid $G\subset {ℝ}^d$ is the set of all intervals in $G$ (cf. Definitions 2 and 5). The cardinality of the domain is huge relative to the cardinality $\left|G\right|$ of $G$ even when $d=2$ ; cf. [2, Theorem 31]. This computational intractability suggests seeking alternative approaches to computing the GPD.

In order to study the complexity associated to computing the GPD, it is useful to consider its classical one-parameter counterpart, where for a filtration of a simplicial complex with $N$ simplices, its persistence diagram contains at most $N$ points. This observation leads to the question: Given a $d$-parameter simplicial filtration, could the cardinality of its GPD (more precisely, the support of the GPD) also be bounded by a polynomial in the number of simplices in the filtration? In what follows, we make this question more precise.

Let $K$ be an abstract simplicial complex, and let $\mathrm{\Delta }K$ be the set of subcomplexes of $K$ ordered by inclusion. A monotone map $ℱ:{ℝ}^d\to \mathrm{\Delta }K$ such that there exists a $p\in {ℝ}^d$ with ${ℱ}_p:=ℱ(p)=K$ is called a ($d$-parameter simplicial) filtration (of $K$). The number of simplices in the filtration $ℱ$ is defined as the number of simplices in $K$.

If $ℱ$ is finite, then for each homology degree $m\in {\mathbb{Z}}_{\ge 0}$, the persistence module ${\mathrm{H}}_m(ℱ;𝔽):{ℝ}^d\to {\mathrm{𝐯𝐞𝐜}}_{𝔽}$ is finitely presentable (cf. Definition 3 and Remark 4). This guarantees that the $𝒎$-th GPD of any finite $d$-parameter filtration is well-defined as an integer-valued function on a finite subset of intervals of ${ℝ}^d$ (cf. Definition 5 and Remark 7), denoted by ${\mathrm{dgm}}_m(ℱ)$. By the size of ${\mathrm{dgm}}_m(ℱ)$ we mean the cardinality of the support of ${\mathrm{dgm}}_m(ℱ)$, i.e. $|\{I\in \mathrm{Int}({ℝ}^d):{\mathrm{dgm}}_m(ℱ)(I)\ne 0\}|$ (cf. Definition 2). Since the notion of the GPD reduces to that of the persistence diagram when $d=1$ [22, Section 3], in this case, the size of the GPD becomes the number of points in the persistence diagram. Our question is as follows.

Note that when $d=1$, the answer to the question is yes, and $k$ can be taken to be $1$, in which case we compute the persistence diagram directly at the simplicial filtration level [28]. If the answer is also yes when $d\ge 2$, it might be possible to compute the GPD of multi-parameter filtrations directly and much more efficiently without relying on the GRI of the persistence module ${\mathrm{H}}_m(ℱ;𝔽):{ℝ}^d\to {\mathrm{𝐯𝐞𝐜}}_{𝔽}$.

Throughout this paper, $P=(P,\le )$ is a poset, regarded as the category whose objects are the elements of $P$, and for any pair $p,q\in P$, there exists a unique morphism $p\to q$ if and only if $p\le q$. All vector spaces in this paper are over a fixed field $𝔽$. Let ${\mathrm{𝐯𝐞𝐜}}_{𝔽}$ denote the category of finite-dimensional vector spaces and linear maps over $𝔽$. A functor $P\to {\mathrm{𝐯𝐞𝐜}}_{𝔽}$ will be referred to as a persistence module over $P$ or simply a $𝑷$-module. A morphism between $P$-modules is a natural transformation between the $P$-modules. For any $P$-modules $M$ and $N$, their direct sum $M\oplus N$ is defined pointwisely. A $P$-module $M$ is trivial if $M(p)=0$ for all $p\in P$, and we write $M=0$. A nontrivial $P$-module $M$ is indecomposable if the assumption $M\cong M^{\prime }\oplus M^{\prime \prime }$ for some $P$-modules $M^{\prime }$ and $M^{\prime \prime }$ implies that either $M^{\prime }=0$ or $M^{\prime \prime }=0$. By Krull-Remak-Schmidt-Azumaya’s theorem [6, 9], any $P$-module is isomorphic to a direct sum of indecomposable $P$-modules, and this decomposition is unique up to isomorphism and permutation of summands.

For any $p\le q$ in $P$, the set $[p,q]:=\{r\in P:p\le r\le q\}$ is called a segment. The collection of all segments (resp. intervals) in $P$ will be denoted by $\mathrm{Seg}(P)$ (rep. $\mathrm{Int}(P)$). It is not difficult to see that $\mathrm{Seg}(P)\subset \mathrm{Int}(P)$.

Given any $I\in \mathrm{Int}(P)$, the interval module ${𝔽}_I$ is the $P$-module, with

Every interval module is indecomposable [10, Proposition 2.2]. A $P$-module $M$ is called interval-decomposable if it is isomorphic to a direct sum of interval modules. The barcode of an interval decomposable $P$-module $M\cong {⨁}_{j\in J}{𝔽}_{I_j}$ is defined as the multiset $\mathrm{barc}(M):=\{I_j:j\in J\}$.

For $p\in P$, let $p^{\uparrow }$ (resp. $p^{\downarrow }$) denote the set of points $q\in P$ such that $p\le q$ (resp. $q\le p$). Clearly, both $p^{\uparrow }$ and $p^{\downarrow }$ belong to $\mathrm{Int}(P)$.

Any $P$-module $M$ admits both a limit and a colimit [48, Chapter V]: A limit of $M$, denoted by $\underleftarrow{\lim }M$, consists of a vector space $L$ together with a collection of linear maps ${\{{\pi }_p:L\to M(p)\}}_{p\in P}$ such that

A colimit of $M$, denoted by $\underrightarrow{\lim }M$, consists of a vector space $C$ together with a collection of linear maps ${\{i_p:M(p)\to C\}}_{p\in P}$ such that

Both $\underleftarrow{\lim }M$ and $\underrightarrow{\lim }M$ satisfy certain universal properties, making them unique up to isomorphism.

Let us assume that $P$ is connected. The connectedness of $P$ alongside the equalities given in Equations (2) and (3) imply that $i_p\circ {\pi }_p=i_q\circ {\pi }_q:L\to C$ for any $p,q\in P$. This fact ensures that the canonical limit-to-colimit map ${\psi }_M:\underleftarrow{\lim }M⟶\underrightarrow{\lim }M$ given by $i_p\circ {\pi }_p$ for any $p\in P$ is well-defined. The (generalized) rank of $M$ is defined to be²²2This construction was considered in the study of quiver representations [43]. $\mathrm{rank}(M):=\mathrm{rank}({\psi }_M)$, which is finite as for any $p\in P$. The rank of $M$ is a count of the “persistent features” in $M$ that span the entire indexing poset $P$ [40].

Now, we refine the rank of a $P$-module, which is a single integer, into an integer-valued function. Options for the domain of the function include $\mathrm{Seg}(P)$ or the larger set $\mathrm{Int}(P)$.

We also remark that, in Definition 5, by replacing all instances of $\mathrm{Int}(P)$ by $\mathrm{Seg}(P)$, we obtain the notions of the rank invariant and its signed barcode [12, 13, 18].

Item i: If $P$ is finite, then $\mathrm{Int}(P)$ is finite. Thus, the claim directly follows from the Möbius inversion formula [57]. Item ii: This statement is precisely that of [22, Theorem C(iii)]. Item iii: In the setting of Item i, the uniqueness is also a direct consequence of the Möbius inversion formula. In the setting of Item ii, the uniqueness is proved in [22, Proposition 3.2].  $◀$

We also remark that if $P$ is a finite poset, the condition given in Equation 4 holds if and only if

where $\mu$ is the Möbius function of the poset $(\mathrm{Int}(P),\supseteq )$; see [61, Section 3.7] for a general reference on Möbius inversion, and [40] for a discussion of Möbius inversion in this specific context.

We define the size of ${\mathrm{rk}}_M$, denoted by $\parallel {\mathrm{rk}}_M\parallel$, as the cardinality of its support. Likewise, the size of ${\mathrm{dgm}}_M$ is defined as the cardinality of its support and is denoted by $\parallel {\mathrm{dgm}}_M\parallel$.

In establishing results in later sections, we will utilize the following well-known concrete formulation for the limit of a $P$-module $M$ (see, for instance, [39, Appendix E]):

A join (a.k.a. least upper bound) of $S\subseteq P$ is an element $q_0\in P$ such that (i) $s\le q_0$, for all $s\in S$, and (ii) for any $q\in P$, if $s\le q$ for all $s\in S$, then $q_0\le q$. A meet (a.k.a. greatest lower bound) of $S\subseteq P$ is an element $r_0\in P$ such that (i) $r_0\le s$ for all $s\in S$, and (ii) for any $r\in P$, if $r\le s$ for all $s\in S$, then $r\le r_0$. If a join and a meet of $S$ exist, then they are unique. Hence, whenever they exist, we refer to them as the join (denoted by $\bigvee S$) and the meet (denoted by $\bigwedge S$), respectively. When $S$ consists of exactly two points $s_1$ and $s_2$, we also use $s_1\vee s_2$ and $s_1\wedge s_2$ instead of $\bigvee S$ and $\bigwedge S$, respectively. A lattice is a poset such that for any pair of elements, their meet and join exist. For any $n\in {\mathbb{Z}}_{\ge 0}$, let . By a finite $d$-d grid lattice, we mean a poset isomorphic to the lattice $[n_1]\times [n_2]\times \mathrm{\cdots }\times [n_d]$ for some $n_1,n_2,\mathrm{\cdots },n_d\in {\mathbb{Z}}_{\ge 0}$.

Let $p$ and $q$ be any two points in a poset $P$. We say that $q$ covers $p$ if and there is no $r\in P$ such that . By $\mathrm{Cov}(p)$, we denote the set of all points $q\in P$ that cover $p$.

A subposet $L\subset P$ (resp. $U\subset P$) is called a lower (resp. upper) fence of $P$ if $L$ is connected, and for any $q\in P$, the intersection $L\cap q^{\downarrow }$ (resp. $U\cap q^{\uparrow }$) is nonempty and connected [25, Definition 3.1].

Let $I$ be any subset of $P$. By $\min (I)$ and $\max (I)$, we denote the collections of minimal and maximal elements of $I$, respectively. A zigzag poset of $n$ points is ${\bullet }_1\leftrightarrow {\bullet }_2\leftrightarrow \mathrm{\dots }{\bullet }_{n-1}\leftrightarrow {\bullet }_n$ where $\leftrightarrow$ stands for either $\le$ or $\ge$.

We consider the cases of $m=0$ and $m\ge 1$ separately.

Fix $n\in {\mathbb{Z}}_{\ge 0}$. Let $K:=K_n$ be the simplicial complex on the vertex set $K^0=\{z_0,z_1,\mathrm{\dots },z_n\}$ that consists of the 1-simplices $\{z_i,z_j\}$ () and their faces. We define a filtration $ℱ:={ℱ}_n$ of $K$ over ${[n]}^2$ as follows. For $(i,j)\in {[n]}^2$, let (see Figure 1):

Let $M:={\mathrm{H}}_0(ℱ;𝔽):{[n]}^2\to {\mathrm{𝐯𝐞𝐜}}_{𝔽}$. Then, we have:

Let $i\in [n]$. Then, for every $(x,y)\in {[n]}^2$ that covers $(i,n-i)$, we have that

In what follows, we use ${\iota }_i$ in place of ${\iota }_i^n$. Now, we consider the following two intervals of ${[n]}^2$ (see Figure 1):

By proving the following claims, we complete the proof for the case of $m=0$.

First, assume that there exists a point $p\in J-U$. Then, by the construction of $M$, $dim(M(p))=0$ and thus ${\mathrm{rk}}_M(J)=0$ by monotonicity of ${\mathrm{rk}}_M$ (Remark 8 Item i). Next, assume that $J=U$. Since ${\mathrm{rk}}_M(U)=\mathrm{rank}({\underleftarrow{\lim }M|}_U\to {\underrightarrow{\lim }M|}_U)$, it suffices to show ${\underleftarrow{\lim }M|}_U=0$. Again, since $D={\min }_{\mathrm{ZZ}}(U)$ , by Lemma 11, it suffices to show that ${\underleftarrow{\lim }M|}_D=0$. By Equation (8), the diagram ${M|}_D$ is given by

From this, it is not difficult to see that ${\underleftarrow{\lim }M|}_D=0$: For $p\in D$, let ${\pi }_p:{\underleftarrow{\lim }M|}_D\to M(p)$ be the canonical projection. For any $i=0,\mathrm{\dots },n$ and for any $v\in {\underleftarrow{\lim }M|}_D$, let ${\pi }_{(i,n-i)}(v)=:(v_1^i,v_2^i,\mathrm{\dots },v_n^i)\in {𝔽}^n=M(i,n-i)$. Then, Equations (2) and (8) imply the following pair of equalities for each $i=1,\mathrm{\dots },n$:

and thus $v_i^i=v_i^{i-1}=0$ for $i=1,\mathrm{\dots }n$. From this, we deduce that $v_j^i=0$ for all $i=0,1,\mathrm{\dots },n$ and $j=1,2,\mathrm{\dots },n$. Therefore, ${\pi }_{(i,n-i)}(v)=0$ for all $i=0,1,\mathrm{\dots },n$ and in turn $v=0$. Since $v\in {\underleftarrow{\lim }M|}_D$ was arbitrary, we have ${\underleftarrow{\lim }M|}_D=0$.

$\mathrm{⊲}$

Consider the following intervals of ${[n]}^2$ (see Figure 2):

Since $J⊊U$, there exists $i\in [n]$ such that $J\subseteq U_i$. Fix such $i$. Since $\max (J)=\{(n,n)\}$, by Lemma 11, we have the isomorphism ${\underrightarrow{\lim }M|}_J\stackrel{(\ast )}{\cong }M(n,n)$. Observe that for every $p\in J\subseteq U_i$, $\{z_i\}\in {ℱ}_p$. Hence, by Convention 9 and the definition of $M$, we have that

Clearly, this tuple ${([z_i])}_{p\in J}$ maps to $[z_i]\in {\mathrm{H}}_0({ℱ}_{(n,n)};𝔽)=M(n,n)$ via the limit-to-colimit map of $M$ over $J$, followed by the isomorphism $(\ast )$. Since $[z_i]\in M(n,n)$ is nonzero and $dimM(n,n)=1$ (cf. Equation 7), we have that ${\mathrm{rk}}_M(J)=1$, as desired.  $\mathrm{⊲}$

We have:

$\mathrm{⊲}$ For each nonempty $S\subset [n]$, we define $U_S:={\bigcap }_{i\in S}{U}_i$, which is an interval of ${[n]}^2$.

Let $I:=U_S$. When $|S|=1$, there exists $i\in [n]$ such that $I=U_i$. We already proved that ${\mathrm{dgm}}_M(U_i)={(-1)}^{1+1}=1$. If $|S|>1$, then

as desired. The number of nonempty subsets $S\subset [n]$ is $2^{n+1}-1$ and each $S$ corresponds to the interval $U_S$ such that ${\mathrm{dgm}}_M(U_S)\ne 0$. Hence, $\parallel {\mathrm{dgm}}_0(ℱ)\parallel =\parallel {\mathrm{dgm}}_M\parallel \ge 2^{n+1}-1.$ In particular, there is no $k\in {\mathbb{Z}}_{\ge 0}$ such that $2^{n+1}-1\in O(N^k)$ for $N:=(n^2+n)/2$, the number of simplices in the filtration $ℱ$, completing the proof. $\mathrm{⊲}$

Let $K^{\prime }:=K_{n,m}$ be the smallest simplicial complex on the vertex set $\{x_0,\mathrm{\cdots },x_n,y_0,\mathrm{\cdots },y_m\}$, containing all $m$-simplices $\tau ,{\tau }_{ij}$, and $(m+1)$-simplices ${\sigma }_{ij}$ that are the underlying sets of the following oriented simplices (see Figure 3a):

For $0\le k\le n$, let $L_k$ be the $m$-dimensional subcomplex of $K^{\prime }$, whose $m$-simplices are exactly $\tau$ and $\{{\tau }_{kj}:0\le j\le m\}$ (see Figure 3a).

We define the filtration ${ℱ}^{\prime }:={ℱ}_{n,m}^{\prime }:{[n]}^2\to \mathrm{\Delta }{K}^{\prime }$ ($=\mathrm{\Delta }{K}_{n,m}$) as (see Figure 3b):

Note that, for each $0\le i\le n$, the $m$-chain $c_i={\tau }^{+}-{\sum }_{j=0}^m{(-1)}^j{\tau }_{ij}^{+}$ in $C_m(K^{\prime };𝔽)$ satisfies $\partial c_i=0$, i.e. $c_i$ is an $m$-cycle. Moreover, ${\mathrm{H}}_m(L_i;𝔽)$, which is isomorphic to $Z_m(L_i;𝔽)$, is the 1-dimensional vector space generated by the homology class $[c_i]$.

Let $N:={\mathrm{H}}_m({ℱ}^{\prime };𝔽):{[n]}^2\to {\mathrm{𝐯𝐞𝐜}}_{𝔽}$. We claim that $N$ is isomorphic to $M$, given in Equation 7. Indeed,

and for each pair $p\le q$ in ${[n]}^2$, $N(p\le q)\cong M(p\le q)$. Therefore, there is no $k\in {\mathbb{Z}}_{\ge 0}$ such that $\parallel {\mathrm{dgm}}_m({ℱ}^{\prime })\parallel =\parallel {\mathrm{dgm}}_N\parallel =\parallel {\mathrm{dgm}}_M\parallel =2^{n+1}-1\notin O(N^k)$ for $N$, the number of simplices in the filtration ${ℱ}^{\prime }$, which belongs to $O(n^{m+2})$. $◀$

In order to prove Theorem 13 for the case where $d>2$, we utilize a result from [12, Section 3.2] and techniques present in [22, Section 3]. See the full version [38] for details.