Asymptotic Bayes risk of semi-supervised learning with uncertain labeling

Victor Léger
Laboratoire d'Informatique de Grenoble

Université Grenoble alpes

Grenoble, France

Romain Couillet
Laboratoire d'Informatique de Grenoble

Université Grenoble alpes

Grenoble, France

This article considers a semi-supervised classification setting on a Gaussian mixture model, where the data is not labeled strictly as usual, but instead with uncertain labels. Our main aim is to compute the Bayes risk for this model.
We compare the behavior of the Bayes risk and the best known algorithm for this model. This comparison eventually gives new insights over the algorithm.

classification, random matrix theory, semi-supervised learning, statistical physics

§ INTRODUCTION

Semi-supervised learning (SSL) is an extension of the conventional supervised learning paradigm by augmenting the (labeled) training data set with unlabeled data, which then “unsupervisably” serve to boost learning performance. SSL has long been considered to be a powerful tool to make use of large amounts of unlabeled data [1].

However, some work also point out the lack of theoretical understanding of these methods [2, 3, 4]. Even by considering a mere Gaussian mixtures model (which is one of the simplest possible parametric model one could consider for a classification problem), well-known methods such as Laplacian regularization appears to be uneffective to learn from unlabeled data [5].

Fortunately, advances in Random Matrix Theory (RMT) has been exploited to design better methods, by proposing fundamental corrections of known algorithms [6], and even extend them, for instance by considering uncertain labeling [7].

Simultaneously, another field of research has focused on analysing Gaussian mixtures model with statistical physics. Such analysis brings an optimal bound for a given problem, meaning that any possible algorithm cannot reach a better performance [8, 9]. These optimal bounds are a precious tool to understand whether an algorithm has poor performances because of its design or because of the inherent difficulty of the problem it tries to solve.

Therefore, the objectives of this article are twofolds :

* Compute the Bayes risk in the case of uncertain data labeling, inspired by the work of [9].

* Use the knowledge of this optimal bound to further understand the behavior of the algorithm of [7], which performances have been proven to be close to the optimal bound.

For simplicity reasons, the model presented in this article is a single-task model, but it is worth to note that most of the conclusions remain true in a multi-task setting, as the previous works it is based on are multi-task models [9, 7].

The remainder of the article is organized as follows. Section <ref> introduces the model, the assumptions and the aim of the next sections. Section <ref> states our main theorem, and gives interpretation of this theorem. Section <ref> gives a succinct proof of the main theorem. Finally, Section <ref> displays simulations of both the optimal bound and the algorithm presented in [7].

§ MODEL AND MAIN OBJECTIVE

We consider a semi-supervised binary classification task with training samples $\mX=[\mX_\ell,\mX_u]\in\R^{p\times n}$ which consists of a set of $n_\ell$ labeled data samples $\mX_\ell = \{\vx_{i}\}_{i=1}^{n_\ell}$ and a set of $n_u$ unlabeled data points $\mX_u = \{\vx_{i}\}_{i=n_\ell+1}^n$. Each labeled data point $\mathbf{x}_{i}$ has an associated couple $(d_{i1},d_{i2})$ of pre-estimated probabilities that the vector belongs to one class or the other, such that $d_{i1}+d_{i2}=1$. The goal of the classification task is to predict the genuine class of unlabeled data $\mathbf{X}_u$. In this context, we are interested in computing the Bayes risk of the classification task, the minimal classification error achievable for each unlabeled sample $\vx_i$ with the available data :

\begin{equation}
\inf_{\hat{y}_i} \mathbb{P}(\hat{y}_i \neq y_i)
\end{equation}

where $\hat{y}_i=\mathbb{E}\left[y_i|\mX\right]$ is the label prediction made for the sample $\vx_i$.

[On the data distribution]

The columns of the data matrix $\mX$ are independent Gaussian random variables. Specifically, the data samples $\left(\vx_1,\dots,\vx_n\right)$ are i.i.d. observations such that $\vx_i \in \mathcal{C}_j \Leftrightarrow \vx_i \sim \mathcal{N}(\vmu_j,\mI_p)$ where $\mathcal{C}_j^{t}$ denotes the Class $j$. We assume that the number of data in each class is the same. We further define the quantity $\lambda=\frac{1}{4}\|\vmu_1-\vmu_2\|^2$, which is called the signal to noise ratio (SNR).

We study our model in a large dimensional setting, where the dimension and the amount of data have the same order of magnitude, which is practically the case with modern data.

[Growth Rate]

As $n\to \infty$ :

* $p/n \to c>0$

* $n_\ell/n \to \eta$

With our notations, in a single-task setting, and assuming that the probability couples of labeled data are either $(0,1)$ or $(1,0)$ (the data is labeled with complete certainty), it has been proved in [9] that under the previous assumptions, as $p \to \infty$, the Bayes risk converges to

\begin{equation}
\label{eq:bayes_mt}
\mathcal{Q}(\sqrt{q_u}),
\end{equation}

where $\mathcal{Q}(x)=\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{-\frac{u^2}{2}} \,\mathrm{d}u$, and the couple $(q_u,q_v)$ satisfies the following equations:

\begin{align}
q_u &= \lambda\frac{\lambda c q_v}{1+\lambda c q_v} \label{eq:overlaps_mt_u} \\
q_v &= \eta + (1-\eta)F(q_u), \label{eq:overlaps_mt_v}
\end{align}

with $F(q)=\mathbb{E}\left[\text{tanh}(\sqrt{q}Z+q)\right]$, $Z\sim\mathcal{N}(0,1)$.

Our goal in the remainder of this article is to derive an equivalent result in the more general case where data is not labeled with certainty.
Let us define, for each datapoint $\vx_i$, $\epsilon_i=d_{i2}-d_{i1} \in [-1,1]$. This quantity is enough to charaterize the couple of probabilities, as $d_{i1}+d_{i2}=1$. We observe that $|\epsilon|=1$ means that the data is labeled with certainty in a class, while $\epsilon=0$ means that the data is unlabeled.

To get equation (<ref>), it is needed to compute the quantity $\hat{y}_i = \mathbb{E}\left[y_i|\mX\right]$, which is the estimation of $y_i$ with the available data $\mX$. In the proof (presented in Section <ref>), a trick allows to compute this quantity as a function of $q_u$, and the labeling information is expressed through the prior distribution of $y$.

* For data labeled with certainty, it is know that $y_i=-1$ or $+1$, so  the prior is either $\delta(t-1)$ or $\delta(t+1)$.

* For unlabeled data, the prior is uniform over $\{-1,+1\}$. Or equivalently, the distribution function is

\begin{equation*}
\frac{1}{2}\delta(t-1)+\frac{1}{2}\delta(t+1).
\end{equation*}

* When the data is not labeled with certainty but with a probability couple $(d_{i1},d_{i2})$, the prior distribution of $y_i$ becomes

\begin{equation}
\label{eq:distrib}
\end{equation}

The following section states our main theorem using this last prior distribution.

§ MAIN RESULTS

Under the previous assumptions, as $p \to \infty$,

* The Bayes risk converges to

\begin{equation}
\label{eq:bayes}
\mathcal{Q}(\sqrt{q_u}),
\end{equation}

where $\mathcal{Q}(x)=\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{-\frac{u^2}{2}} \,\mathrm{d}u$.

* The overlaps $q_u,q_v$ satisfy the following equations

\begin{align}
q_u &= \lambda\frac{\lambda c q_v}{1+\lambda c q_v} \label{eq:overlaps_u} \\
q_v &= \lim_{n\to\infty} \frac{1}{n}\sum_{i=1}^n F_{\epsilon_i}(q_u) \label{eq:overlaps_v}
\end{align}

with $F_\epsilon(q)= \mathbb{E}\left[\psi_{\epsilon}(q+\sqrt{q}Z)\right]$, $Z\sim\mathcal{N}(0,1)$ and

\begin{equation*}
\psi_\epsilon(t)=\frac{\text{tanh}(t) + {\epsilon}^2\left(1-\text{tanh}(t)-\text{tanh}^2(t)\right)}{1 - {\epsilon}^2\text{tanh}^2(t)}.
\end{equation*}

A sketch of the proof of Theorem <ref> is given in Section <ref>.
The function $F_\epsilon$ is similar to the previous function $F$, but the expression of $\psi_\epsilon$ is not easy to understand as it is.

The function $\psi_{\epsilon}$ can be put in the following (more convenient) form :

\begin{align*}
\psi_{\epsilon}(t)&=\text{tanh}(t) + \epsilon^2\left(1-\text{tanh}(t)\right) \\
&-(1-\epsilon^2)(1-\text{tanh}(t))\sum_{k\geq 1} \epsilon^{2k}\text{tanh}^{2k}(t).
\end{align*}

The function $F_\epsilon$ can be approximated by :

\begin{equation}
\tilde{F}_\epsilon(q)= \mathbb{E}\left[\tilde{\psi}_{\epsilon}(q+\sqrt{q}Z)\right],
\end{equation}

with $Z\sim\mathcal{N}(0,1)$ and

\begin{equation}
\tilde{\psi}_\epsilon(t)=\text{tanh}(t)+\epsilon^2(1-\text{tanh}(t)).
\end{equation}

[view/h=120, colorbar horizontal, grid=major, yshift=5cm, ylabel=$q$, xlabel=$|\epsilon|$, zlabel=$\frac{|F_\epsilon(q)-\tilde{F}_\epsilon(q)}{F_\epsilon(q)}$, width=1, height=0.65, legend style=fill opacity=0.8, text opacity=1, font=, legend pos=north west]
3 [surf, shader=interp] table approx_error.dat;

Relative error of the approximation $\tilde{F}_\epsilon(q)\simeq F_\epsilon(q)$. The error is at most $7\%$, and shrinks for either $\epsilon=0$, $\epsilon=1$ or large $q$

Figure <ref> gives an idea of the quality of the approximation made in Remark <ref>. However, it is worth to note that its purpose is not to replace the original formula from Theorem <ref>, as that formula is already tractable and can be computed easily. Instead, Remark <ref> intend to bring a simpler formula that conveys an understanding of the key role of quantity $\epsilon^2$.

As $q_u$ and $q_v$ are related to each other, one could also worry that a small error in equation (<ref>) could lead to a completely different solution for $q_u$ and $q_v$. Fortunately, if one replaces the solution $(q_u^\star,q_v^\star)$ of the system by another solution $(q_u^\star+\Delta q_u,q_v^\star+\Delta q_v)$, then we have $|\frac{\Delta q_u}{q_u^\star}| \leq |\frac{\Delta q_v}{q_v^\star}|$. This means that a small variation of $q_v$ leads to an even smaller variation of $q_u$.

With the previous approximation of the function $F_\epsilon$, one can approximate the equation (<ref>) :

\begin{equation}
\label{eq:qv_final}
q_v \simeq \bar{\epsilon}^2 + (1-\bar{\epsilon}^2)F(q_u)
\end{equation}

\begin{align*}
\bar{\epsilon}^2 &= \frac{1}{n}\sum_{i=1} {\epsilon_i}^2 \\
F(q) &= \mathbb{E}\left[\text{tanh}(q+\sqrt{q}Z)\right] \\
\end{align*}

Proof: The function $\tilde{F}_{\epsilon_i}$ described in Remark <ref> can be expressed with function $F$ :

\begin{align*}
\tilde{F}_{\epsilon_i}(q)&=\mathbb{E}\left[\text{tanh}(q+\sqrt{q}Z) + {\epsilon_i}^2(1-\text{tanh}(q+\sqrt{q}Z))\right] \\
&={\epsilon_i}^2 + \mathbb{E}\left[\text{tanh}(q+\sqrt{q}Z)\right](1-{\epsilon_i}^2)\\
&={\epsilon_i}^2 + (1-{\epsilon_i}^2)F(q)
\end{align*}

By mixing the results of Theorem <ref> and Remark <ref>, one gets asymptotically

\begin{align*}
q_v &\simeq \frac{1}{n}\sum_{i=1}^n \tilde{F}_{\epsilon_i}(q_u) \\
&=\frac{1}{n}\sum_{i=1}^n \left[{\epsilon_i}^2 + (1-{\epsilon_i}^2)F(q)\right] \\
&=\bar{\epsilon}^2 + \left(1-\bar{\epsilon}^2\right)F(q)
\end{align*}

Corollary <ref> enables an easy interpretation of Theorem <ref>. Indeed, the value of $q_v$ given by equation (<ref>) is similar to equation (<ref>), with $\eta=\bar{\epsilon}^2$. One can check that :

* $\epsilon^2=0 \leftrightarrow$ unlabeled data $\leftrightarrow \eta=0$

* $\epsilon^2=1 \leftrightarrow$ data labeled with certainty $\leftrightarrow \eta=1$

If all samples are labeled with the same value $\epsilon$, then it is equivalent to a task for which one would have a proportion $\epsilon^2$ of data labeled with certainty and a proportion $1-\epsilon^2$ of unlabeled data.

To go further, $F(q_u)$ can be understood as a quantity that expresses how useful unlabeled data are, relatively to labeled data. Indeed, if $F(q_u)=1$, unlabeled data brings as much information as labeled data. Interestingly, this quantity $F(q_u)$ only depends on $q_u$, which itself related to the Bayes risk of the classification task. Thus, usefulness of unlabeled data only depends on how well the task can be performed. Figure <ref> displays the quantity $F(q_u)$ as a function of Bayes risk.

[grid=major,yshift=5cm,ylabel=$F(q_u)$,xlabel=Bayes risk,width=1,height=0.75,legend style=fill opacity=0.8,text opacity=1,font=,legend pos=north west]
[blue] table[x=eps,y=y] usefulness.dat;

Usefulness of unlabeled data as a function of the Bayes risk of the task. Interestingly, the only criterion to determinate the effectiveness of unlabeled data is how solvable the task is. The lower the Bayes risk is, the more unlabeled data are useful to perform the task.

§ SKETCH OF THE PROOF

The proof of Theorem <ref> is really similar to the one performed in [9], as (<ref>) and (<ref>) remain the same, but the main difference lays in the expression of $q_v$, that must be adapted. As in the original proof, $q_v=\langle\hat{\vy},\vy\rangle$ is the overlap of the signal $\vy=(y_i)_i$, and we have asymptotically, through the law of large numbers :

\begin{equation}
\label{eq:proof_1}
q_v = \lim_{n\to\infty} \frac{1}{n}\sum_{i=1}^n \mathbb{E}\left[\hat{y}_iy_i\right]
\end{equation}

where $\hat{y}_i = \mathbb{E}\left[y_i|\mX\right]$ is the MMSE estimator of $y_i$.

Then, a key lemma for the proof is the following.

Estimating $y_i$ from $\mX$ is asymptotically equivalent to estimating the signal $y_i$ from the output of a Gaussian channel with SNR $q_u$. Let us consider the following Gaussian channel

\begin{equation*}
U_i = \sqrt{\lambda}S_i+Z_i
\end{equation*}

with $\lambda=q_u$ the SNR, $S_i$ the signal and $Z_i\sim\mathcal{N}(0,1)$.
Then computing the overlap $\mathbb{E}\left[\hat{y}_iy_i\right]$ of $y_i$ is equivalent to computing the overlap $\mathbb{E}\left[\hat{S}_iS_i\right]$ of $S_i$, with $\hat{S}_i = \mathbb{E}\left[S_i|U_i\right]$

Thus, one has

\begin{equation}
\label{eq:proof_2}
\mathbb{E}\left[\hat{y}_iy_i\right] = \mathbb{E}\left[\hat{S}_iS_i\right]
\end{equation}

The signal $S_i$ follows the same distribution than $y_i$ :

\begin{equation*}
S_i \sim \left\{
\begin{array}{lr}
-1 ~ \text{with probability} ~ d_{i1},\\
+1 ~ \text{with probability} ~ d_{i2}
\end{array}
\right.
\end{equation*}

\begin{equation*}
\mathbf{E}\left[S_i|U_i\right] = \frac{d_{i1}e^{\sqrt{\lambda}U_i} - d_{i2}e^{-\sqrt{\lambda}U_i}}{d_{i1}e^{\sqrt{\lambda}U_i} + d_{i2}e^{-\sqrt{\lambda}U_i}}
\end{equation*}

Using $\epsilon_i=d_{i1}-d_{i2}$, one gets $\mathbf{E}\left[S_i|U_i\right] = f_{\epsilon_i}(\sqrt{\lambda}U_i)$, with

\begin{equation*}
f_{\epsilon}(t) = \frac{\text{tanh}(t) + \epsilon}{1 + \epsilon\text{tanh}(t)}
\end{equation*}

\begin{align}
\label{eq:proof_3}
&\mathbf{E}\left[S_i\mathbf{E}\left[S_i|U_i\right]\right] = \mathbf{E}\left[S_if_{\epsilon_i}(\lambda S_i+\sqrt{\lambda} Z_i)\right] \nonumber \\
&= d_{i1}\mathbf{E}\left[f_{\epsilon_i}(\lambda+\sqrt{\lambda} Z_i)\right] - d_{i2}\mathbf{E}\left[f_{\epsilon_i}(-\lambda+\sqrt{\lambda} Z_i)\right] \nonumber \\
&= d_{i1}\mathbf{E}\left[f_{\epsilon_i}(\lambda+\sqrt{\lambda} Z_i)\right] - d_{i2}\mathbf{E}\left[f_{\epsilon_i}(-(\lambda+\sqrt{\lambda} Z_i))\right] \nonumber \\
&= \mathbf{E}\left[\psi_{\epsilon_i}(\lambda+\sqrt{\lambda} Z_i)\right]
\end{align}

with $\psi_{\epsilon_i}(t) = d_{i1}f_{\epsilon_i}(t) - d_{i2}f_{\epsilon_i}(-t)$

More precisely,

\begin{align*}
\psi_{\epsilon_i}(t)&=d_{i1}\frac{\text{tanh}(t) + {\epsilon_i}}{1 + {\epsilon_i}\text{tanh}(t)} - d_{i2}\frac{-\text{tanh}(t) + {\epsilon_i}}{1 - {\epsilon_i}\text{tanh}(t)} \\
%&=d_{i1}\frac{(\text{tanh}(t) + {\epsilon_i})(1 - {\epsilon_i}\text{tanh}(t))}{(1 - {\epsilon_i}^2\text{tanh}^2(t))} \\
%&+d_{i2}\frac{(\text{tanh}(t) - {\epsilon_i})(1 + {\epsilon_i}\text{tanh}(t))}{(1 - {\epsilon_i}^2\text{tanh}^2(t))} \\
&=(d_{i1}+d_{i2})\frac{\text{tanh}(t) - {\epsilon_i}^2\text{tanh}(t)}{1 - {\epsilon_i}^2\text{tanh}^2(t)} \\
&+(d_{i1}-d_{i2})\frac{{\epsilon_i}(1 - \text{tanh}^2(t))}{1 - {\epsilon_i}^2\text{tanh}^2(t)} \\
%&=\frac{\text{tanh}(t) - {\epsilon_i}^2\text{tanh}(t)}{(1 - {\epsilon_i}^2\text{tanh}^2(t))} \\
%&+{\epsilon_i}^2\frac{1 - \text{tanh}^2(t)}{(1 - {\epsilon_i}^2\text{tanh}^2(t))} \\
&=\frac{\text{tanh}(t) + {\epsilon_i}^2\left(1-\text{tanh}(t)-\text{tanh}^2(t)\right)}{1 - {\epsilon_i}^2\text{tanh}^2(t)} \\
%&=\frac{\text{tanh}(t) + {\epsilon_i}^2\left(1-\text{tanh}(t)\right)}{(1 - {\epsilon_i}^2\text{tanh}^2(t))} - \frac{{\epsilon_i}^2\text{tanh}^2(t)}{1 - {\epsilon_i}^2\text{tanh}^2(t)} \\
%&=\text{tanh}(t) + {\epsilon_i}^2\left(1-\text{tanh}(t)\right)\sum_{k\geq 0} {\epsilon_i}^{2k}\text{tanh}^{2k}(t) \\
%&+{\epsilon_i}^2\text{tanh}^2(t)\sum_{k\geq 1} {\epsilon_i}^{2k}\text{tanh}^{2k}(t) \\
%&=\text{tanh}(t) + {\epsilon_i}^2\left(1-\text{tanh}(t)\right) \\
%&-(1-{\epsilon_i}^2)(1-\text{tanh}(t))\sum_{k\geq 1} {\epsilon_i}^{2k}\text{tanh}^{2k}(t).
\end{align*}

Combining (<ref>), (<ref>) and (<ref>), we obtain (<ref>).

§ SIMULATIONS AND APPLICATIONS

The objective of this section is to confront theoretical results of Section <ref> and the algorithm described in [7], which will be from now on refered to as optimal algorithm. The common idea of the following experiments is that the optimal algorithm is expected to behave similarly to the optimal bound studied in Section <ref>.

As we have seen in Section <ref>, different labeling settings can lead to the same value of $\bar{\epsilon}^2$. Let us start with only unlabeled data and data labeled with certainty. Then,

\begin{equation}
\label{eq:sim1}
\bar{\epsilon}^2 = \eta,
\end{equation}

and we obtain a classification error $E$.
Now, let us assume that all the labeled data is labeled with the same confidence $\kappa<1$. The total number of data $n$ stays unchanged. For different values of $\kappa$, if one wants to achieve the same error $E$, then more labeled data will be needed as $\kappa$ decreases. Indeed, reaching the same performance means obtaining the same $q_u$, and therefore $q_v$, as the task does not change beyond that. We recall that $q_v \simeq \bar{\epsilon}^2 + (1-\bar{\epsilon}^2)F(q_u)$, and in our context, $F(q_u)$ does not change. Consequently, to obtain the same error $E$, $\bar{\epsilon}^2$ must stay constant. Moreover, we have

\begin{equation}
\label{eq:sim2}
\bar{\epsilon}^2 = \frac{n_\ell}{n}(2\kappa-1)^2
\end{equation}

By combining (<ref>) and (<ref>), one gets

\begin{equation}
\label{eq:sim3}
n_\ell = \frac{\eta}{(2\kappa-1)^2}n
\end{equation}

For a given value of $\eta$, $(2\kappa-1)^2$ must be no smaller than $\eta$, otherwise even a fully labeled dataset would not allow to reach $\bar{\epsilon}^2=\eta$.

Figure <ref> displays both empirical and theoretical values of $n_\ell$ as a function of $\kappa$ in this setting. The theoretical value is given by (<ref>), and the empirical one is computed by incrementing $n_\ell$ (and decrementing $n_u$) until the error given by the optimal algorithm gets below $E$. The match between empirical and theoretical curves show that Corollary <ref> helps to understand the behavior of the algorithm.

[grid=major,yshift=5cm,ylabel=Number of labeled data $n_\ell$,xlabel=Confidence $\kappa$ in labeled data,xmin=0.45,width=1,height=0.75,legend style=fill opacity=0.8,text opacity=1,font=,legend pos=south west]
+[blue, only marks] table[x=conf1,y=nl1] epsilon_conf_emp.dat;
+[red, only marks] table[x=conf2,y=nl2]epsilon_conf_emp.dat;
+[green, only marks] table[x=conf3,y=nl3] epsilon_conf_emp.dat;
+[black, only marks] table[x=conf4,y=nl4] epsilon_conf_emp.dat;
+[cyan, only marks] table[x=conf5,y=nl5] epsilon_conf_emp.dat;
[blue] table[x=x1,y=y1] epsilon_conf_th.dat;
[red] table[x=x2,y=y2] epsilon_conf_th.dat;
[green] table[x=x3,y=y3] epsilon_conf_th.dat;
[black] table[x=x4,y=y4] epsilon_conf_th.dat;
[cyan] table[x=x5,y=y5] epsilon_conf_th.dat;

Number of labeled data $n_\ell$ needed to perform the same performance, as a function of the confidence in the data labeling, for different values of $\eta$ ($n=1000, p=200, \lambda=0.25$). The empirical values are displayed in dots, and theoretical prediction (built on the results of Section <ref>) in plain line. The least reliable the data is, the more data is needed to reach the same performance.

The other takeaway message of Section <ref> is that the usefulness of unlabeled data, expressed through the quantity $F(q_u)$, only depends on the Bayes risk of the task, and therefore the final classification error of the optimal algorithm. In order to understand the contribution of unlabeled data, one could be interested in computing the reduction of the classification error by using the semi-supervised version of the optimal algorithm instead of the fully supervised one. With the aim in mind, we will consider the two following quantities:

* The absolute error reduction

\begin{equation}
\frac{E_{\text{sup}}-E_{\text{semi-sup}}}{E_{\text{sup}}}
\end{equation}

which is the tangible error reduction one can expect by adopting the semi-supervised method instead of the fully supervised one.

* The error reduction relatively to oracle bayes risk

\begin{equation}
\frac{E_{\text{sup}}-E_{\text{semi-sup}}}{E_{\text{sup}}-E_{\text{oracle}}}
\end{equation}

which reflects how much of the way to oracle error has been done by adopting the semi-supervised method instead of the fully supervised one,

where $E_{\text{oracle}}$ is the bayes risk one can expect when the centers of distributions $\vmu_1$ and $\vmu_2$ are known. More precisely, oracle error is given by the formula

\begin{equation}
E_{\text{oracle}} = \mathcal{Q}(\sqrt{\lambda}).
\end{equation}

Leaving out the parameter $\eta$, the main parameters that drive the final error are $\lambda$ and $c$, as we can see in (<ref>). Therefore, Figures <ref> and <ref> display the two kinds of error reduction presented above, respectively as functions of $\lambda$ and $c$.

[grid=major,yshift=5cm,ylabel=Error reduction,ytick=0.0,0.2,0.4,0.6,0.8,yticklabels=$0\%$,$20\%$,$40\%$,$60\%$,$80\%$,xlabel=$\lambda$,width=1,height=0.75,legend style=fill opacity=0.8,text opacity=1,font=,legend pos=south east]
[blue,solid] table[x=lambda,y=algo_abs] reduction_lambda.dat;
[red,densely dashed] table[x=lambda,y=algo_oracle] reduction_lambda.dat;
[blue,densely dotted] table[x=lambda,y=bound_abs] reduction_lambda.dat;
[red,dotted] table[x=lambda,y=bound_oracle] reduction_lambda.dat;

Percentage of error reduction by using the semi-supervised algorithm instead of the supervised one, as a function of the SNR $\lambda$ ($n=p=200, \eta=0.2$). The easier the task is, the higher the semi-supervised contribution is, because the classification error is lower.

[grid=major,yshift=5cm,ylabel=Error reduction,ytick=0.0,0.2,0.4,0.6,0.8,yticklabels=$0\%$,$20\%$,$40\%$,$60\%$,$80\%$,xlabel=$c$,width=1,height=0.75,legend style=at=(0.97,0.75),fill opacity=0.8,text opacity=1,font=]
[blue,solid] table[x=alpha,y=algo_abs] reduction_alpha.dat;
[red,densely dashed] table[x=alpha,y=algo_oracle] reduction_alpha.dat;
[blue,densely dotted] table[x=alpha,y=bound_abs] reduction_alpha.dat;
[red,dotted] table[x=alpha,y=bound_oracle] reduction_alpha.dat;

Percentage of error reduction by using the semi-supervised algorithm instead of the supervised one, as a function of the ratio $c=n/p$ ($\lambda=2, p=200, \eta=0.2$). As $c$ grows, the semi-supervised algorithm is more and more effective comparatively to the supervised one, relatively to oracle error, because the classification error is lower and oracle error stays constant. However, if the oracle error ceases to be the reference, then the contribution of semi-supervised decreases for high values of $c$, because both algorithms edge closer to the oracle bound, which stays far from zero.

In Figure <ref>, it is clear that the error reduction is higher when $\lambda$ grows, for both types of error reduction. Intuitively, a higher
SNR means a lower final error, and consequently a higher contribution of unlabeled data to the classification.

Meanwhile in Figure <ref>, the two types of error reduction do not behave similarly. In this case, the oracle error is constant, and both errors $E_{\text{sup}}$ and $E_{\text{semi-sup}}$ get close to $E_{\text{oracle}}$ as $c$ grows. Therefore, there is not much to gain by adopting the semi-supervised algorithm, as we are already close to the oracle bound with the supervised one. However, the error reduction relatively to oracle still increases when $c$ grows. We see that the understanding of what remains to be improved plays a key role in Figure <ref>.

§ CONLUDING REMARKS

Figuring out the link between the performances of an algorithm and its optimal bound gives precious insights. In our case, the algorithm behaves similarly to its optimal bound, giving strong insight that the algorithm is indeed near optimal. So if the algorithm gives poor performances, it simply  means that the problem is inherently too hard to solve. Therefore, the interest of computing such optimal bounds is clear. By knowing in advance how far from optimal an algorithm is, one can avoid spending too much energy to solve a problem which turns out to be a dead-end.

Furthermore, the similarity of behavior between the algorithm and the bound allows to understand the algorithm from an other perspective. Indeed, results from Sections <ref> and <ref> provide a new understanding on when semi-supervised learning is truly useful, and when it is not.

[1]
O. Chapelle, B. Schölkopf, and A. Zien, Semi-Supervised Learning.1em plus 0.5em minus 0.4emThe MIT Press, 09 2006. [Online]. Available: <https://doi.org/10.7551/mitpress/9780262033589.001.0001>

[2]
B. Shahshahani and D. Landgrebe, “The effect of unlabeled samples in reducing the small sample size problem and mitigating the hughes phenomenon,” IEEE Transactions on Geoscience and Remote Sensing, vol. 32, no. 5, pp. 1087–1095, 1994.

[3]
F. G. Cozman and I. Cohen, “Risks of semi-supervised learning: How unlabeled data can degrade performance of generative classifiers,” in Semi-Supervised Learning, 2006. [Online]. Available: <https://api.semanticscholar.org/CorpusID:63547716>

[4]
S. Ben-David, T. Lu, and D. Pál, “Does unlabeled data provably help? worst-case analysis of the sample complexity of semi-supervised learning,” in Annual Conference Computational Learning Theory, 2008. [Online]. Available: <https://api.semanticscholar.org/CorpusID:7670149>

[5]
X. Mai and R. Couillet, “A random matrix analysis and improvement of semi-supervised learning for large dimensional data,” The Journal of Machine Learning Research, vol. 19, no. 1, pp. 3074–3100, 2018.

[6]
——, “Consistent semi-supervised graph regularization for high dimensional data,” Journal of Machine Learning Research, vol. 22, no. 94, pp. 1–48, 2021. [Online]. Available: <http://jmlr.org/papers/v22/19-081.html>

[7]
V. Leger and R. Couillet, “A large dimensional analysis of multi-task semi-supervised learning,” 2024.

[8]
M. Lelarge and L. Miolane, “Asymptotic bayes risk for gaussian mixture in a semi-supervised setting,” 2019.

[9]
M.-T. Nguyen and R. Couillet, “Asymptotic bayes risk of semi-supervised multitask learning on gaussian mixture,” 2023.


# Decomposition of Persistent Homology and Spectral Sequences

Peiqi Yang  Department of Mathematics, The George Washington University
Phillips Hall, 801 22nd St. NW, Room 739, Washington, DC 20052, USA
<EMAIL_ADDRESS>,  Yingfeng Hu  Department of Mathematics, The George
Washington University
Phillips Hall, 801 22nd St. NW, Room 739, Washington, DC 20052, USA
<EMAIL_ADDRESS>and  Hao Wu  Department of Mathematics, The George
Washington University
Phillips Hall, 801 22nd St. NW, Room 739, Washington, DC 20052, USA
<EMAIL_ADDRESS>
###### Abstract.

We study the relation between the persistent homology and the spectral
sequence of a filtered chain complex over a field. Our method is based on a
decomposition of the persistent homology. We demonstrate that, under fairly
general assumptions, these two algebraic structures capture the same
information from the filtered chain complex.

###### Key words and phrases:

filtered chain complex, persistent homology, spectral sequence, exact couple

###### 2020 Mathematics Subject Classification:

Primary 55N31, 55T05

##  1\. Introduction

###  1.1. Background

Filtered chain complexes arise naturally in many applications of algebraic
topology. For example, given a point cloud in a metric space, one can consider
the abstract simplicial complex consisting of all the possible abstract
simplexes with vertices in this cloud. This abstract simplicial complex gives
rise a simplicial chain complex, which, by itself, has trivial homology. But,
when equipped with the filtration induced by the diameters of simplexes, the
filtered chain complex captures much topological information of the point
cloud.

There are two main approaches to extracting homological information from a
filtered chain complex. The more classical approach is via spectral sequences
defined by Jean Leray [3], which are hard to compute in most cases. More
recently, in the study of point clouds, most researchers opt to use the
persistent homology because there are efficient algorithms to compute it [2,
9].

A natural question is how different or similar are the homological data
obtained by these two approaches. Saugata Basu and Laxmi Parida [1]
established explicit relations between the spectral sequences and the
persistent homology for filtered chain complexes over a field. In fact,
similar relations are implicit in the work of the third author [8] in the
context of the Khovanov-Rozansky homology in knot theory. In this paper, we
apply the arguments in [8] to more general filtered chain complexes over
fields and, among other things, recover the results in [1]. Our method is
based on decomposition theorems of persistent homology and spectral sequences,
which allow us to avoid complicated exact sequence arguments and provide a
direct and intuitive explanation why the two approaches yield exactly the same
information from a filtered chain complex over a field under fairly general
assumptions.

###  1.2. Statement of results

In the current paper, we fix a base field $\mathbb{F}$ and consider filtered
chain complexes of $\mathbb{F}$-spaces.

######  Definition 1.1.

A filtered chain complex $(C,d,\mathcal{F})$ over $\mathbb{F}$ consists of

  1. (1)

a $\mathbb{Z}$-graded $\mathbb{F}$-space $C=\bigoplus_{n\in\mathbb{Z}}C_{n}$,

  2. (2)

a differential map $d:C\rightarrow C$ satisfying $d^{2}=0$ and
$d(C_{n})\subset C_{n-1}$,

  3. (3)

an ascending $\mathbb{Z}$-filtration $\mathcal{F}$ on each $C_{n}$ satisfying
$d(\mathcal{F}^{p}C_{n})\subset\mathcal{F}^{p}C_{n-1}$.

We write $\mathcal{F}^{p}C=\bigoplus_{n\in\mathbb{Z}}\mathcal{F}^{p}C_{n}$. We
say that

  * •

$(C,\mathcal{F})$ is locally finite dimensional over $\mathbb{F}$ if
$\dim_{\mathbb{F}}\mathcal{F}^{p}C_{n}<\infty$ for each $p\in\mathbb{Z}$ and
$n\in\mathbb{Z}$,

  * •

$\mathcal{F}$ is bounded below on $C_{n}$ if there is a $p\in\mathbb{Z}$
depending on $n$, such that $\mathcal{F}^{p}C_{n}=0$.

Note that $(\mathcal{F}^{p}C,d|_{\mathcal{F}^{p}C})$ is a subcomplex of the
chain complex $(C,d)$ for all $p\in\mathbb{Z}$. The persistent chain complex
$(PC,d_{x})$ of $(C,d,\mathcal{F})$ [9, Definition 3.1] is defined to be the
direct sum

$(PC,d_{x}):=\bigoplus_{p\in\mathbb{Z}}(\mathcal{F}^{p}C,d|_{\mathcal{F}^{p}C}).$

Let $x$ be a homogeneous indeterminate of degree $1$ acting on $PC$ as the
natural inclusion map
$i^{p}:\mathcal{F}^{p}C\hookrightarrow\mathcal{F}^{p+1}C$ for each
$p\in\mathbb{Z}$. This makes $(PC,d_{x})$ is a chain complex of graded
$\mathbb{F}[x]$-modules, where the homogeneous component of degree $p$ is
$(\mathcal{F}^{p}C,d|_{\mathcal{F}^{p}C})$. The homology $PH:=H(PC,d_{x})$ is
a graded $\mathbb{F}[x]$-module and called the persistent homology of
$(C,d,\mathcal{F})$ [9] .

Our arguments are based on Theorem 1.4. Before stating the theorem, let us
introduce the following notations.

######  Definition 1.2.

Let $M$ be a graded $\mathbb{F}[x]$ module. Then $M||n||\\{s\\}$ is a bigraded
$\mathbb{F}[x]$-module where

  * •

$||\cdot||$ indicates the homological grading,

  * •

$\\{\cdot\\}$ indicates the polynomial degree shift, that is
$\left(M||n||\\{s\\}\right)^{k}=M^{k-s}$.

######  Definition 1.3.

Denoted by $\mathbb{Z}_{+,\infty}=\mathbb{Z}_{+}\cup\\{+\infty\\}$, we assume
$n,s\in\mathbb{Z}$ and $m\in\mathbb{Z}_{+,\infty}$. Define two types of graded
chain complex

$\displaystyle U_{n,s,\infty}\ $ $\displaystyle=\
0\to\mathbb{F}[x]||n||\\{s\\}\to 0$ (1) $\displaystyle U_{n,s,m}\ $
$\displaystyle=\
0\to\mathbb{F}[x]||n+1||\\{s+m\\}\xrightarrow{x^{m}}\mathbb{F}[x]||n||\\{s\\}\to
0$ (2)

where $m=\infty$ in (1) and $0<m<\infty$ in (2).

Our main results are the following.

######  Theorem 1.4.

Let $(PC,d_{x})$ be the persistent chain complex of a filtered chain complex
$(C,d,\mathcal{F})$ over $\mathbb{F}$ satisfying:

  * •

For each $n$, the filtration $\mathcal{F}$ on $C_{n}$ is bounded below;

  * •

$(C,d,\mathcal{F})$ is locally finite dimensional over $\mathbb{F}$.

Then, up to chain homotopy and permutation of factors, $(PC,d_{x})$ can be
uniquely decomposed into a direct sum of graded chain complexes of types (1)
and (2). More precisely, for each $n\in\mathbb{Z}$, there exist
$K_{n}\in\mathbb{Z}_{+,\infty}$ and a unique sequence
$\\{(s_{n}(i),m_{n}(i))\\}_{i=1}^{K_{n}}\subseteq\mathbb{Z}\times\mathbb{Z}_{+,\infty}$
satisfying:

  * •

the set $\\{i\ |\ s_{n}(i)=s\\}$ is finite for all $s\in\mathbb{Z}$ and
$n\in\mathbb{Z}$,

  * •

$s_{n}(i)\leq s_{n}(i+1)$,

  * •

$m_{n}(i)\leq m_{n}(i+1)$ if $s_{n}(i)=s_{n}(i+1)$,

so that

$PC\simeq\bigoplus_{n=-\infty}^{\infty}\bigoplus_{i=1}^{K_{n}}U_{n,s_{n}(i),m_{n}(i)}.$
(3)

Consequently, the persistent homology $PH=H(PC,d_{x})$ can be uniquely
decomposed into a direct sum of

$PH\cong\bigoplus_{n=-\infty}^{\infty}\bigoplus_{i=1}^{K_{n}}H(U_{n,s_{n}(i),m_{n}(i)}).$
(4)

Here, each factor in Decomposition (4) has the form
$H(U_{n,s,\infty})\cong\mathbb{F}[x]||n||\\{s\\}$ or
$H(U_{n,s,m})\cong\mathbb{F}[x]/(x^{m})||n||\\{s\\}$ for $m<\infty$.

The proof of Theorem 1.4 is included in Section 2. Since the spectral
sequences corresponding to the persistent chain complexes $U_{n,s,\infty}$ and
$U_{n,s,m}$ are easy to compute, Theorem 1.4 leads to a direct sum
decomposition of spectral sequences over $\mathbb{F}$ into simple factors.
Denote by $E^{(r)}$ the $r$-th page of the spectral sequence of
$(C,d,\mathcal{F})$ and by $E_{n,s}^{(r)}$ the homogeneous component of
$E^{(r)}$ with homological grading $n$ and $\mathbb{F}[x]$-module grading $s$.

######  Theorem 1.5.

Let $(PC,d_{x})$ be the persistent chain complex of a filtered chain complex
$(C,d,\mathcal{F})$ over $\mathbb{F}$ satisfying:

  * •

For each $n$, the filtration $\mathcal{F}$ on $C_{n}$ is bounded below;

  * •

$(C,d,\mathcal{F})$ is locally finite dimensional over $\mathbb{F}$.

Decomposition (4) of the persistent homology $PH=H(PC,d_{x})$ in Theorem 1.4
induces a direct sum decomposition of the spectral sequence $\\{E^{(r)}\\}$ of
$(C,d,\mathcal{F})$. More precisely, for $r\in\mathbb{Z}_{+,\infty}$ and the
same sequence
$\\{(s_{n}(i),m_{n}(i))\\}_{i=1}^{K_{n}}\subseteq\mathbb{Z}\times\mathbb{Z}_{+,\infty}$
given in Theorem 1.4, we have that,

$E^{(r)}\cong\bigoplus_{n=-\infty}^{\infty}\bigoplus_{i=1}^{K_{n}}E^{(r)}(U_{n,s_{n}(i),m_{n}(i)}),$

where:

  * •

$E^{(r)}(U_{n,s,\infty})\cong\mathbb{F}\|n\|\\{s\\}$ $\forall r\geq 1$, and
consequently $E^{(\infty)}(U_{n,s,\infty})\cong\mathbb{F}\|n\|\\{s\\}$.

  * •

If $m<\infty$, then

$E^{(r)}(U_{n,s,m})\cong\begin{cases}\mathbb{F}||n+1||\\{s+m\\}\oplus\mathbb{F}||n||\\{s\\}&\text{for
}1\leq r\leq m,\\\ 0&\text{for }r>m.\end{cases}$

And, consequently $E^{(\infty)}(U_{n,s,m})\cong 0$.

Comparing the decompositions in Theorems 1.4 and 1.5, one can deduce that the
spectral sequence and the persistent homology determine each other under
fairly general assumptions. We formulate this as the following.

######  Definition 1.6.

The spectral sequence $\\{E^{(r)}\\}$ collapses locally to $E^{(\infty)}$ if
$\\{E_{n,s}^{(r)}\\}$ collapses to $E_{n,s}^{(\infty)}$ for every
$n,s\in\mathbb{Z}$. That is, there exists $r_{n,s}\in\mathbb{Z}_{+}$ such that
$E_{n,s}^{(r)}\cong E_{n,s}^{(\infty)}$ if $r>r_{n,s}$.

######  Definition 1.7.

Let $K_{n}\in\mathbb{Z}_{+,\infty}$ and
$\\{(s_{n}(i),m_{n}(i))\\}_{i=1}^{K_{n}}\subseteq\mathbb{Z}\times\mathbb{Z}_{+,\infty}$
be the unique sequence described in Theorem 1.4. For $n,s\in\mathbb{Z}$ and
$m\in\mathbb{Z}_{+,\infty}$, define the multiplicity of $H(U_{n,s,m})$ in
Decomposition (4) as

$\nu_{n,s,m}:={|}\\{i\ |\ 1\leq i\leq K_{n},\ s_{n}(i)=s,\ m_{n}(i)=m\\}{|}.$

In particular, the multiplicity of $H(U_{n,s,\infty})$ is defined as

$\nu_{n,s,\infty}:={|}\\{i\ |\ 1\leq i\leq K_{n},\ s_{n}(i)=s,\
m_{n}(i)=\infty\\}{|}.$

######  Theorem 1.8.

Let $(PC,d_{x})$ and $\\{E^{(r)}\\}$ be the persistent chain complex and
spectral sequences of a filtered chain complex $(C,d,\mathcal{F})$ over
$\mathbb{F}$ satisfying:

  * •

For each $n$, the filtration $\mathcal{F}$ on $C_{n}$ is bounded below;

  * •

$(C,d,\mathcal{F})$ is locally finite dimensional over $\mathbb{F}$.

Then we have

  1. (1)

$\dim_{\mathbb{F}}E_{n,s}^{(r)}=\nu_{n,s,\infty}+\sum_{m\geq
r}(\nu_{n,s,m}+\nu_{n-1,s-m,m})$, which shows that the persistent homology
determines the spectral sequence.

  2. (2)

The spectral sequence $\\{E^{(r)}\\}$ collapses locally to $E^{(\infty)}$, and

     * (a)

$\nu_{n,s,\infty}=\dim_{\mathbb{F}}E_{n,s}^{(\infty)}$,

     * (b)

$\nu_{n,s,m}=\dim_{\mathbb{F}}E_{n,s}^{(m)}-\dim_{\mathbb{F}}E_{n,s}^{(m+1)}-\nu_{n-1,s-m,m}$.

If the filtration $\mathcal{F}$ is also bounded below on the entire $C$, then
(a) and (b) imply that the spectral sequence determines the persistent
homology, because $\nu_{n,s,m}=0$ for $s\ll 0$ since $\mathcal{F}$ is bounded
below uniformly.

######  Corollary 1.9.

[1, Corollary 2] [2, Spectral Sequence Theorem] Let $(PC,d_{x})$ be the
persistent chain complex of a filtered chain complex $(C,d,\mathcal{F})$ over
$\mathbb{F}$ satisfying:

  * •

For each $n$, the filtration $\mathcal{F}$ on $C_{n}$ is bounded below;

  * •

$(C,d,\mathcal{F})$ is locally finite dimensional over $\mathbb{F}$.

Then for any $r>0$, we have

$dim_{\mathbb{F}}E_{n}^{(r)}=\sum_{s}\left(\nu_{n,s,\infty}+\sum_{m\geq
r}(\nu_{n,s,m}+\nu_{n-1,s,m})\right).$ (5)

Equation (5) is equivalent to the following equation from [1, Corollary 2]:

$dim_{\mathbb{F}}E_{n}^{(r)}(\mathcal{F})=b_{n}(\mathcal{F})+\sum_{t-s\geq
r}(\mu_{n}^{s,t}(\mathcal{F})+\mu_{n-1}^{s,t}(\mathcal{F}))$ (6)

where $b_{n}(\mathcal{F})$ is the persistent Betti number and
$\mu_{n}^{s,t}(\mathcal{F})$ is the persistent multiplicity that are both
defined in [2, VII.1].

Corollary 1.9 follows directly from Corollary 4.1 and Proposition 4.2.

##  2\. Decomposition of Persistent Homology

###  2.1. Persistent chain complexes

Let $(C,d,\mathcal{F})$ be a filtered chain complex over $\mathbb{F}$ defined
in Definition 1.1 and $(PC,d_{x})$ be the correspond persistent chain complex.
For each $p,n\in\mathbb{Z}$, fix an $\mathbb{F}$-subspace $G^{p}_{n}$ of
$\mathcal{F}^{p}C_{n}$ such that
$\mathcal{F}^{p}C_{n}=\mathcal{F}^{p-1}C_{n}\oplus G_{n}^{p}$. Then

$\mathcal{F}^{p}C_{n}=\bigoplus_{q=-\infty}^{p}G_{n}^{q}.$

For $q\leq p$, denote by $\pi^{p,q}_{n}:\mathcal{F}^{p}C_{n}\to G_{n}^{q}$ the
natural projection. Restricting the differential map $d_{n}:C_{n}\to C_{n-1}$
to $G^{p}_{n}$, we have
$d_{n}^{p}:G_{n}^{p}\to\mathcal{F}^{p}C_{n-1}=\bigoplus_{q=-\infty}^{p}G_{n-1}^{q}$.
Define the map $d_{n}^{p,q}:G_{n}^{p}\to G_{n-1}^{q}$ by
$d_{n}^{p,q}=\pi_{n-1}^{p,q}\circ d_{n}^{p}$ for any $p\geq q$. Thus
$d_{n}^{p}=\sum_{q\leq p}d_{n}^{p,q}$.

######  Definition 2.1.

For each $n\in\mathbb{Z}$, we define a graded $\mathbb{F}[x]$-module as
${\mathcal{PC}_{n}=\mathbb{F}[x]\otimes_{\mathbb{F}}C_{n}}$ where
$\mathcal{PC}^{p}_{n}:=\bigoplus_{k\geq 0}x^{k}G^{p-k}_{n}$ is the homogeneous
component of $\mathcal{PC}_{n}$ of degree $p$. $\mathcal{PC}_{n}$ is a graded
$\mathbb{F}[x]$-module for each $n$. Define an $\mathbb{F}[x]$-module map
$(\delta_{x})_{n}:\mathcal{PC}_{n}\to\mathcal{PC}_{n-1}$ such that
$(\delta_{x})_{n}^{p}:=(\delta_{x})|_{G_{n}^{p}}:G^{p}_{n}\to\mathcal{PC}^{p}_{n-1}$
is given by $(\delta_{x})_{n}^{p}=\sum_{q\leq p}x^{p-q}d_{n}^{p,q}$.

Note that $(\delta_{x})_{n}$ is a homogeneous map preserving the module
grading since the degree of $d_{n}^{p,q}$ is $q-p$.

######  Proposition 2.2.

$(\mathcal{PC},\delta_{x})$ is isomorphic to $(PC,d_{x})$. In particular,
$(PC,d_{x})$ is a free $\mathbb{F}[x]$-module.

###### Proof.

Recall that $\mathcal{F}^{p}C_{n}=\bigoplus_{q=-\infty}^{p}G^{p}_{n}$ and
$(PC,d_{x})=\bigoplus_{p\in\mathbb{Z}}(\mathcal{F}^{p}C,d|_{\mathcal{F}^{p}C})$.
We have
$PC_{n}=\bigoplus_{p\in\mathbb{Z}}\mathcal{F}^{p}C_{n}=\bigoplus_{p\in\mathbb{Z}}\left(\bigoplus_{q=-\infty}^{p}G^{q}_{n}\right)$.
For any $n\in\mathbb{Z}$ and any $u\in\mathcal{F}^{p}C_{n}\subset PC_{n}$,
there is a decomposition of $u$ given by $u=\sum_{q\leq p}g_{n}^{q,p}$ where
each $g_{n}^{q,p}\in G_{n}^{q}\subset\mathcal{F}^{p}C_{n}$. Define
$\varphi_{n}:PC_{n}\to\mathcal{PC}_{n}$ by

$\varphi_{n}(u)=\varphi_{n}\left(\sum_{q\leq p}g_{n}^{q,p}\right)=\sum_{q\leq
p}x^{p-q}g_{n}^{q}$

where $g_{n}^{q}=g_{n}^{q,p}$ when viewed as an element of
$G_{n}^{q}\subset\mathcal{PC}_{n}$. This is an $\mathbb{F}$-linear isomorphism
with $\varphi_{n}^{-1}\left(\sum_{q\leq p}x^{p-q}g_{n}^{q}\right)=\sum_{q\leq
p}g_{n}^{q,p}$. Consider $i^{p}:\mathcal{F}^{p}C\to\mathcal{F}^{p+1}C$.
$g_{n}^{q,p}\in G_{n}^{q}\subset\mathcal{F}^{p}C_{n}$ and $g_{n}^{q,p+1}\in
G_{n}^{q}\subset\mathcal{F}^{p+1}C_{n}$ are the same element as $g_{n}^{p}\in
G^{p}_{n}\subset\mathcal{PC}_{n}$. Then $i^{p}(g_{n}^{q,p})=g_{n}^{q,p+1}$
and, for $u\in\mathcal{F}^{p}C_{n}$,

$\displaystyle\varphi_{n}(xu)$
$\displaystyle=\varphi(i^{p}(u))=\varphi_{n}\left(i^{p}\left(\sum_{q\leq
p}g_{n}^{q,p}\right)\right)=\varphi_{n}\left(\sum_{q\leq
p}g_{n}^{q,p+1}\right)$ $\displaystyle=\sum_{q\leq
p}x^{(p+1)-q}g_{n}^{q}=\sum_{q\leq p}x^{p-q+1}g_{n}^{q}$
$\displaystyle=x\cdot\sum_{q\leq p}x^{p-q}g_{n}^{q}=x\cdot\varphi_{n}(u).$

To verify $\varphi$ is a chain map, we have

$\displaystyle\delta_{x}\circ\varphi_{n}(u)$
$\displaystyle=\delta_{x}\left(\sum_{q\leq
p}x^{p-q}g_{n}^{q}\right)=\sum_{q\leq
p}x^{p-q}\cdot(\delta_{x})_{n}^{q}(g_{n}^{q})$ $\displaystyle=\sum_{q\leq
p}x^{p-q}\sum_{k\leq q}x^{q-k}d_{n}^{q,k}(g^{p}_{n})=\sum_{q\leq p}\sum_{k\leq
q}x^{(p-q)+(q-k)}d_{n}^{q,k}(g^{p}_{n})$ $\displaystyle=\sum_{q\leq
p}\sum_{k\leq q}x^{p-k}d_{n}^{q,k}(g^{p}_{n}).$

Note that $d^{q,k}_{n}(g_{n}^{q,p})\in
G_{n-1}^{k}\subset\mathcal{F}^{p}C_{n-1}$. We also have

$\displaystyle\varphi_{n-1}\circ d_{x}(u)$
$\displaystyle=\varphi_{n-1}\left(d|_{\mathcal{F}^{p}C_{n}}\left(\sum_{q\leq
p}g_{n}^{q,p}\right)\right)=\varphi_{n-1}\left(\sum_{q\leq
p}d^{q}_{n}(g_{n}^{q,p})\right)$ $\displaystyle=\varphi_{n-1}\left(\sum_{q\leq
p}\sum_{k\leq q}d^{q,k}_{n}(g_{n}^{q,p})\right)=\sum_{q\leq p}\sum_{k\leq
q}\varphi_{n-1}\left(d^{q,k}_{n}(g_{n}^{q,p})\right)$
$\displaystyle=\sum_{q\leq p}\sum_{k\leq q}x^{p-k}d_{n}^{q,k}(g^{p}_{n}).$

Thus $\delta_{x}\circ\varphi=\varphi\circ d_{x}$ and $\varphi$ is a chain map.

Since $\delta_{x}=\varphi\circ d_{x}\circ\varphi^{-1}$ and $d_{x}\circ
d_{x}=0$, we have $\delta_{x}\circ\delta_{x}=\varphi\circ d_{x}\circ
d_{x}\circ\varphi^{-1}=0$. Note that $\delta_{x}$ preserves the module
grading. Therefore $(\mathcal{PC},\delta_{x})$ is a chain complex of graded
$\mathbb{F}[x]$-modules and isomorphic to $(PC,d_{x})$ induced by $\varphi$. ∎

Proposition 2.2 shows that $(\mathcal{PC},\delta_{x})$ is isomorphic to
persistent chain complex $(PC,d_{x})$. We will no longer distinguish between
these two in the rest of this manuscript.

###  2.2. Existence of the decomposition

######  Definition 2.3.

A graded $\mathbb{F}$-space $M$ is locally finite dimensional if $M^{k}$ is
finite dimensional over $\mathbb{F}$ for every $k\in\mathbb{Z}$, where $M^{k}$
is the $\mathbb{F}$-subspace of $M$ consisting of all homogeneous elements of
degree $k$.

######  Lemma 2.4.

Let $\mathbb{F}[x]$ be the graded polynomial ring with $deg(x)=1$. Assume that
$M$ is a free graded $\mathbb{F}[x]$-module satisfying:

  * •

$\mathbb{F}[x]$-grading of $M$ is bounded below,

  * •

$M$ is locally finite dimensional over $\mathbb{F}$.

Then $M$ admits a countable homogeneous basis.

Denote by $\lambda_{M}^{k}$ the $\mathbb{F}$-dimension of $(M/xM)^{k}$, where
$(M/xM)^{k}$ is $\mathbb{F}$-subspace of $M/xM$ consisting of all elements of
grading $k$. Assume that $g$ is the lowest $\mathbb{F}[x]$-grading of $M$.
Define the sequence $L_{M}$ as

$L_{M}=(\underbrace{g,\cdots,g}_{\lambda_{M}^{g}},\underbrace{g+1,\cdots,g+1}_{\lambda_{M}^{g+1}},\cdots,\underbrace{g+k,\cdots,g+k}_{\lambda_{M}^{g+k}},\cdots).$

Let $E$ be a countable collection of homogeneous elements of M such that the
cardinality of $E\cap M^{k}$ is finite for every $k$. After arranging the
elements of $E$ in non-decreasing order by their degrees, the degrees of
elements in $E$ form a non-decreasing sequence $L_{E}$. Then $L_{B}=L_{M}$ for
any homogeneous basis $B$ of $M$.

###### Proof.

$M$ has a homogeneous basis since free graded modules over polynomial rings
with grading bounded below admit homogeneous bases [7, Lemma 4.4] [5, Page
130, Exercise 3].

Let $B$ be any homogeneous basis for $M$. To prove that $L_{B}=L_{M}$, it
suffices to show that $\pi(B)$ is a homogeneous $\mathbb{F}$-basis for
$(M/xM)$, where $\pi:M\xrightarrow{}(M/xM)$ is the canonical projection. Since
$\pi$ is surjective, $\pi(B)$ spans $(M/xM)$. Assume that $\pi(B)$ is not
$\mathbb{F}$-linearly independent, then there exist $P>0$ with $b_{p}\in B$,
$f_{p}\in\mathbb{F}$ and $g_{p}\in\mathbb{F}[x]$ for all $1\leq p\leq P$, such
that

$\sum_{p=1}^{P}(f_{p}-g_{p}x)b_{p}=0$ (7)

and $f_{p}-g_{p}x\neq 0$ for each $p$. By the $\mathbb{F}[x]$-linearly
independence of $B$, all coefficients in equation (7) are zero. We have that
$f_{p}-xg_{q}=0$, which implies that $f_{p}$ and $g_{p}$ are both equal to
zero for all $p$. This is a contradiction.

∎

######  Lemma 2.5.

Assume that

${\cdots}$${M}$${N}$${\cdots}$$\scriptstyle{d}$

is a chain complex of free graded $\mathbb{F}[x]$-module satisfying:

  * •

Its differential $d$ is homogeneous and preserves the $\mathbb{F}[x]$-grading;

  * •

The $\mathbb{F}[x]$-grading of $M$ and $N$ are bounded below;

  * •

$M$ and $N$ are locally finite dimensional over $\mathbb{F}$.

Then $M$ has a homogeneous $\mathbb{F}[x]$-basis $V\sqcup W$ and $N$ has a
homogeneous $\mathbb{F}[x]$-basis $\overline{W}\sqcup R$ satisfying

  * (I)

$d(v)=0$ for every $v\in V$;

  * (II)

There exists a bijection $\bar{~{}}:~{}W\to\overline{W}$ mapping each $w\in W$
to a $\bar{w}\in\overline{W}$ such that $d(w)=x^{m}\bar{w}$ for some non-
negative integer $m$ depending on $w$;

Considering the submodules $M^{V}$, $M^{W}$, $N^{\overline{W}}$ and $N^{R}$
generated by $V$, $W$, $\overline{W}$, and $R$, the chain complex decomposes
into a direct sum of three subchain complexes as

${\cdots}$${M^{V}}$${0}$${0}$${M^{W}}$${N^{\overline{W}}}$${0}$${0}$${N^{R}}$${\cdots}$$\scriptstyle{d}$$\scriptstyle{d}$${\bigoplus}$$\scriptstyle{d}$${\bigoplus}$

###### Proof.

We prove this by induction. Let $B^{(0)}$ be a homogeneous basis for $M$ and
$\tilde{B}^{(0)}$ be a homogeneous basis for $N$, respectively. By Lemma 2.4,
$L_{M}$ is the non-decreasing sequence of degrees in any homogeneous basis of
$M$. Let sets $W^{(0)}$, $V^{(0)}$ and $\overline{W}^{(0)}$ be empty sets. Let
$Z^{(0)}=B^{(0)}$ and $R^{(0)}=\tilde{B}^{(0)}$. We will construct by
induction the sets $B^{(l)}$, $\tilde{B}^{(l)}$, $V^{(l)}$, $W^{(l)}$,
$O^{(l)}$, $Z^{(l)}$, $\overline{W}^{(l)}$ and $R^{(l)}$, satisfying the
following conditions:

  * (i)

$B^{(l)}$ is a homogeneous basis for $M$ and $\tilde{B}^{(l)}$ is a
homogeneous basis for $N$;

  * (ii)

$O^{(l)}=V^{(l)}\sqcup W^{(l)}$, $B^{(l)}=Z^{(l)}\sqcup O^{(l)}$ and
$\tilde{B}^{(l)}=\overline{W}^{(l)}\sqcup R^{(l)}$;

  * (iii)

$V^{(l-1)}\subset V^{(l)}$, $W^{(l-1)}\subset W^{(l)}$,
$\overline{W}^{(l-1)}\subset\overline{W}^{(l)}$ and $R^{(l-1)}\supset
R^{(l)}$;

  * (iv)

$d(Z^{(l)})\subset\mathrm{Span}_{\mathbb{F}[x]}R^{(l)}$;

  * (v)

$d(v)=0$ for every $v\in V^{(l)}$;

  * (vi)

There exists a bijection $\bar{~{}}:~{}W^{(l)}\to\overline{W}^{(l)}$ mapping
each $w\in W^{(l)}$ to a $\bar{w}\in\overline{W}^{(l)}$ such that
$d(w)=x^{m}\bar{w}$ for some positive integer $m$ depending on $w$;

  * (vii)

The sequence $L_{O^{(l)}}$ for set of homogeneous elements111Notation follows
Lemma 2.4. is consist of the first $l$ terms of $L_{M}$.

In each iteration, we remove an element from $Z^{(l)}$ with the lowest grading
and add it to $O^{(l)}$. We will induct on the size of organized base set
$O^{(l)}$. Conditions (i)-(vii) are trivially true when $l=0$. Then assume
that we have updated all these sets satisfying conditions (i)-(vii) after $l$
steps. By (vii), $|O^{(l)}|=|V^{(l)}|+|W^{(l)}|=l$. We will then construct
$B^{(l+1)}$, $\tilde{B}^{(l+1)}$, $V^{(l+1)}$, $W^{(l+1)}$,
$\overline{W}^{(l+1)}$, $O^{(l+1)}$, $Z^{(l+1)}$ and $R^{(l+1)}$.

Let $w$ be an element of $Z^{(l)}$ with the lowest module grading, whose
degree by Lemma 2.4 is the $(l+1)$-th term of $L_{M}$.

If $d(w)=0$, we will do the following updates:

$V^{(l+1)}=V^{(l)}\cup\\{w\\},\ W^{(l+1)}=W^{(l)},\
\overline{W}^{(l+1)}=\overline{W}^{(l)},$ $Z^{(l+1)}=Z^{(l)}\setminus\\{w\\},\
O^{(l+1)}=V^{(l+1)}\cup W^{(l+1)},\ R^{(l+1)}=R^{(l)},$
$B^{(l+1)}=Z^{(l+1)}\cup O^{(l+1)},\
\tilde{B}^{(l+1)}=\overline{W}^{(l+1)}\cup R^{(l+1)}.$

This update preserves condition (v) and automatically satisfies all other
conditions.

If $d(w)\neq 0$, assume that $d(w)=\sum_{e\in E}\alpha_{e}e$ where $E$ is a
finite subset of $R^{(l)}$ by (iv), and each $\alpha_{e}=c_{e}x^{m_{e}}$ is a
non-zero monomial in $\mathbb{F}[x]$. Let $\hat{e}$ be an element with the
highest module grading in $E$. Note that $m_{e}=\deg(w)-\deg(e)$ and therefore
$m_{\hat{e}}=\min_{e\in E}m_{e}$. Define

$\bar{w}=\frac{d(w)}{x^{m_{\hat{e}}}}=c_{\hat{e}}\hat{e}+\sum_{e\in
E,e\neq\hat{e}}c_{e}x^{m_{e}-m_{\hat{e}}}e.$

and do the following updates:

$V^{(l+1)}=V^{(l)},\ W^{(l+1)}=W^{(l)}\cup\\{w\\},\
\overline{W}^{(l+1)}=\overline{W}^{(l)}\cup\\{\bar{w}\\},$
$R^{(l+1)}=R^{(l)}\setminus\\{\hat{e}\\},\ O^{(l+1)}=V^{(l+1)}\cup W^{(l+1)},\
\tilde{B}^{(l+1)}=R^{(l+1)}\cup\overline{W}^{(l+1)}.$

Then $\tilde{B}^{(l+1)}$ is still a homogeneous basis for $N$. Thus the
bijection $\ \bar{\textbullet}\ $ in (vi) is extend by $w\mapsto\bar{w}$. Note
that $d(w)=x^{m}\bar{w}$. It remains to construct $Z^{(l+1)}$ and show it
satisfies condition (iv).

By conditions (iv) in the previous step, any element in $\overline{W}^{(l)}$
will not appear in the image of $z\in Z^{(l)}$ since $z$ is not in $W^{(l)}$
according to condition (ii). Now consider for each $z$ in
$Z^{(l)}\setminus\\{w\\}$, then $d(z)$ is a linear combination of base
elements in $R^{(l)}$. We have $d(z)=\beta_{z}\bar{w}+\sum_{e\in
E_{z}}\beta_{e}e$, where $\beta$ are the coefficient monomials and $E_{z}$ is
a finite subset of $R^{(l+1)}$. Notice that
$\deg(\beta_{z})=\deg(z)-\deg(\bar{w})\geq\deg(w)-\deg(\bar{w})=m_{\hat{e}}$.
Define

$z^{\prime}=z-\frac{\beta_{z}}{x^{m_{\hat{e}}}}w.$

Then
$d(z^{\prime})=d(z)-\frac{\beta_{z}}{x^{m_{\hat{e}}}}d(w)=d(z)-\beta_{z}\bar{w}=\sum_{e\in
E_{z}}\beta_{e}e$ and therefore
$d(z^{\prime})\in\mathrm{Span}_{\mathbb{F}[x]}R^{(l+1)}$. Now we update
$Z^{(l+1)}$ and $B^{(l+1)}$ by

$Z^{(l+1)}=\\{z^{\prime}|z\in Z^{(l)}\setminus\\{w\\}\\}$

and

$B^{(l+1)}=Z^{(l+1)}\cup O^{(l+1)}.$

Hence $d(Z^{(l+1)})\subset\mathrm{Span}_{\mathbb{F}[x]}R^{(l+1)}$. $B^{(l+1)}$
is obtained from $B^{(l)}$ by an invertible $\mathbb{F}[x]$-linear
transformation, so $B^{(l+1)}$ is also a basis for $M$. This proves condition
(iv). Note that $|O^{(l+1)}|=|V^{(l)}|+|\\{w\\}|+|W^{(l)}|=l+1$. Therefore
conditions (i)-(vi) work for all $B^{(l)}$, $\tilde{B}^{(l)}$, $V^{(l)}$,
$W^{(l)}$, $\overline{W}^{(l)}$, $O^{(l)}$, $Z^{(l)}$ and $R^{(l)}$ for each
natural number $l$.

Recall that $M^{k}$ is finite dimensional for every $k$. Let $g$ be the lowest
grading of $M$, which is the first term in $L_{M}$. Thus
$\bigoplus_{k=g}^{K}M^{k}$ is finite dimensional for any $K\geq g$. Set
$l_{K}=\dim_{\mathbb{F}}\bigoplus_{k=g}^{K}M^{k}=\sum_{k=g}^{K}\lambda_{M}^{k}$
where $\lambda_{M}^{k}$ is given in Lemma 2.4. Observe that
$|O^{(l_{K})}|=l_{K}$ and

$\bigoplus_{k=g}^{K}M^{k}\subseteq\mathrm{Span}_{\mathbb{F}[x]}O^{(l_{K})}$

since $Z^{(l_{K})}$ contains only elements that have degree larger than $K$.
Thus

$M=\bigoplus_{k=g}^{\infty}M^{k}\subseteq\mathrm{Span}_{\mathbb{F}[x]}\bigcup_{l=0}^{\infty}O^{(l)}.$

Then any element in $M$ can be written as a linear combination of elements in
some $O^{(l)}$. Let

$V=\bigcup_{l=0}^{\infty}V^{(l)}\ \text{and}\
W=\bigcup_{l=0}^{\infty}W^{(l)},$

then this is our desired $V$ and $W$. Note that $V\sqcup
W=\bigcup_{l=0}^{\infty}O^{(l)}$. Each $O^{(l)}$ is a subset of a homogeneous
basis $B^{(l)}$ and therefore linearly independent. Hence $V\sqcup W$ is
indeed a homogeneous basis for $M$.

In each step, we have constructed a bijection between $W^{(l)}$ and
$\overline{W}^{(l)}$. Define

$\overline{W}=\bigcup_{l=0}^{\infty}\overline{W}^{(l)}\ \text{and}\
R=\bigcap_{l=0}^{\infty}R^{(l)}.$

Let $g^{\prime}$ be the lowest module grading of $N$. Fix a $K\geq
g^{\prime}$,
$\tilde{B}^{(l)}\cap\left(\bigoplus_{k=g^{\prime}}^{K}N^{k}\right)$ is finite
for every $l$ since $N$ is locally finite dimensional. Note that
$R^{(l-1)}\supset R^{(l)}$ for each $l$ from condition (iii). Then for there
exists a positive integer $l_{0}$ depending on $K$, such that

$R^{(l_{0})}\cap\left(\bigoplus_{k=g^{\prime}}^{K}N^{k}\right)=\left(\bigcap_{l=0}^{\infty}R^{(l)}\right)\cap\left(\bigoplus_{k=g^{\prime}}^{K}N^{k}\right)=R\cap\left(\bigoplus_{k=g^{\prime}}^{K}N^{k}\right).$

Therefore $\left(\bigoplus_{k=g^{\prime}}^{K}N^{k}\right)$ has a basis
$\tilde{B}^{(l_{0})}\cap\left(\bigoplus_{k=g^{\prime}}^{K}N^{k}\right)=(\overline{W}\sqcup
R)\cap\left(\bigoplus_{k=g^{\prime}}^{K}N^{k}\right)$. $\overline{W}\sqcup R$
spans $N$ as $K$ growing. Hence $\overline{W}\sqcup R$ is indeed a homogeneous
basis for $N$. This concludes the constructions of $V$, $W$, $\overline{W}$
and $R$.

Notice that after the construction of $\overline{W}$ and $R$, we obtained a
subchain complex

${0}$${N^{R}}$${\cdots}$$\scriptstyle{d}$

where $N^{R}$ is the submodule generated by $R$ in $N$. Denote by $N^{\prime}$
be the term before $M$ in the chain complex and consider the other direct
summand

${\cdots}$${N^{\prime}}$${M}$${N^{\overline{W}}}$${0.}$$\scriptstyle{d}$$\scriptstyle{d}$

If $d(u)\neq 0$ for any $u\in N^{\prime}$, then $d(u)=\sum_{v\in
V}\gamma_{v}v+\sum_{w\in W}\gamma_{w}w$ where all but finitely many
$\gamma_{v}$ and $\gamma_{w}$ are $0$. We claim that $\gamma_{w}=0$ for each
$w$. Otherwise, since $d(v)=0$ for each $v\in V$ and $d(w)=x^{m_{w}}\bar{w}$
for each $w\in W$, we have

$0=(d\circ d)(u)=\sum_{w\in W}\gamma_{w}d(w)=\sum_{w\in
W}\gamma_{w}x^{m_{w}}\bar{w}.$

Since each $\bar{w}\in\overline{W}$ is an $\mathbb{F}[x]$-base element,
$\gamma_{w}$ must be $0$ if $w\in W$. Therefore we will further decompose the
subchain complex into

${\cdots}$${M^{V}}$${0}$$\scriptstyle{d}$

where $M^{V}$ is the submodule in $M$ generated be $V$, and

${0}$${M^{W}}$${N^{\overline{W}}}$${0}$$\scriptstyle{d}$

where $M^{W}$ is the submodule in $M$ generated by $W$ as well as
$N^{\overline{W}}$ is the submodule in $N$ generated by ${\overline{W}}$.

∎

######  Proposition 2.6.

Assume that

$(A,d)=\leavevmode\hbox to147.83pt{\vbox
to16.42pt{\pgfpicture\makeatletter\hbox{\hskip 73.91678pt\lower-8.25955pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{\offinterlineskip{}{}{{{}}{{}}{{}}{{}}}{{{}}}{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-73.91678pt}{-8.15971pt}\pgfsys@invoke{
}\hbox{\vbox{\halign{\pgf@matrix@init@row\pgf@matrix@step@column{\pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding&&\pgf@matrix@step@column{\pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding\cr\hfil\hskip
8.05554pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.75pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\cdots}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip
8.05554pt\hfil&\hfil\hskip 33.73618pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.43066pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${A_{n}}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip
9.7362pt\hfil&\hfil\hskip 36.0695pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-7.76399pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${A_{n-1}}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip
12.06953pt\hfil&\hfil\hskip 32.05551pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.75pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\cdots}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
8.05554pt\hfil\cr}}}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}{{{{}}}{{}}{{}}{{}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} {}{ {}{}{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.39998pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{{}}\pgfsys@moveto{-57.6057pt}{-5.65971pt}\pgfsys@lineto{-34.40569pt}{-5.65971pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-34.2057pt}{-5.65971pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-51.38344pt}{-1.68474pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{$\scriptstyle{d_{n+1}}$} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{ {}{}{}}{}{ {}{}{}}
{{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.39998pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{{}}\pgfsys@moveto{-14.13332pt}{-5.65971pt}\pgfsys@lineto{9.0667pt}{-5.65971pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{9.26668pt}{-5.65971pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.3555pt}{-2.44583pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{$\scriptstyle{d_{n}}$}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{ {}{}{}}{}{ {}{}{}}
{{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{{}}{}{}{}{{{}{}}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.39998pt}\pgfsys@invoke{
}{}{}{}{}{{}}{}{}{{}}\pgfsys@moveto{34.00572pt}{-5.65971pt}\pgfsys@lineto{57.20573pt}{-5.65971pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}}}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{57.40572pt}{-5.65971pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{41.11688pt}{-2.01807pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{$\scriptstyle{d_{n-1}}$} }}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$

is a chain complex of free graded $\mathbb{F}[x]$-module satisfying:

  * •

Its differential $d$ is homogeneous and preserves the $\mathbb{F}[x]$-grading
of $A$;

  * •

For each $n$, the $\mathbb{F}[x]$-grading of $A_{n}$ is bounded below;

  * •

For each $n$, $A_{n}$ is locally finite dimensional over $\mathbb{F}$.

Then every $A_{n}$ has a homogeneous $\mathbb{F}[x]$-basis that is the
disjoint union of three subsets $V_{n}$, $W_{n}$ and $\overline{W}_{n}$,
satisfying the following conditions:

  * (I)

$d(v)=0$ for every $v\in V_{n}$;

  * (II)

There exists a bijection $\bar{~{}}:~{}W_{n}\to\overline{W}_{n-1}$ mapping
each $w\in W_{n}$ to a $\bar{w}\in\overline{W}_{n-1}$ such that
$d(w)=x^{m}\bar{w}$ for some non-negative integer $m$ depending on $w$.

###### Proof.

By Lemma 2.4, each $A_{n}$ has a homogeneous basis. Since for each $n$,
$A_{n}$ satisfies all the conditions in Lemma 2.5, we may apply this lemma to

${\cdots}$${A_{1}}$${A_{0}}$${\cdots}$$\scriptstyle{d_{2}}$$\scriptstyle{d_{1}}$$\scriptstyle{d_{0}}$

We will obtain $\mathbb{F}[x]$-basis sets $\tilde{V}_{1}\sqcup W_{1}$ for
$A_{1}$ and $\overline{W}_{0}\sqcup R_{0}$ for $A_{0}$ with a direct sum
decomposition

${\cdots}$${\tilde{A}_{1}}$${0}$${0}$${\mathcal{U}_{1}}$${\overline{\mathcal{U}}_{0}}$${0}$${0}$${\tilde{A}_{0}}$${\cdots}$$\scriptstyle{d_{2}}$$\scriptstyle{d_{1}}$${\bigoplus}$$\scriptstyle{d_{0}}$${\bigoplus}$

Here $\tilde{A}_{1}$, $\mathcal{U}_{1}$, $\overline{\mathcal{U}}_{0}$ and
$\tilde{A}_{0}$ are submodules generated by sets $\tilde{V}_{1}$, $W_{1}$,
$\overline{W}_{0}$ and $R_{0}$ respectively.

We will prove this proposition by two inductions separately on the upward
branch

${\cdots}$${A_{2}}$${\tilde{A}_{1}}$${0}$$\scriptstyle{d_{3}}$$\scriptstyle{d_{2}}$

and the downward branch

${0}$${\tilde{A}_{0}}$${A_{-1}}$${\cdots}$$\scriptstyle{d_{0}}$$\scriptstyle{d_{-1}}$

For the upward branch, we first apply Lemma 2.5 to

${\cdots}$${A_{2}}$${\tilde{A}_{1}}$${0.}$$\scriptstyle{d_{3}}$$\scriptstyle{d_{2}}$

It decomposes into

${\cdots}$${\tilde{A}_{2}}$${0}$${0}$${\mathcal{U}_{2}}$${\overline{\mathcal{U}}_{1}}$${0}$${0}$${F_{1}}$${0}$$\scriptstyle{d_{3}}$$\scriptstyle{d_{2}}$${\bigoplus}$${\bigoplus}$

where $\tilde{A}_{2}$, $\mathcal{U}_{2}$, $\overline{\mathcal{U}}_{1}$ and
$F_{1}$ are the submodules generated by sets $\tilde{V}_{2}$, $W_{2}$,
$\overline{W}_{1}$ and $R_{1}$ respectively. Note that $\tilde{V}_{2}\sqcup
W_{2}$ is a basis for $A_{2}=\tilde{A}_{2}\oplus\mathcal{U}_{2}$ and
$\overline{W}_{1}\sqcup R_{1}$ is a basis for
$\tilde{A}_{1}=\overline{\mathcal{U}}_{1}\oplus F_{1}$. $R_{1}$ satisfies
condition (I) in $A_{1}$ thus let $V_{1}=R_{1}$. Now we have obtained $V_{1}$,
$W_{1}$ and $\overline{W}_{1}$. Since $W_{1}$ generates $\mathcal{U}_{1}$ and
$\overline{W}_{1}\sqcup V_{1}$ is a basis for $\tilde{A}_{1}$, $V_{1}\sqcup
W_{1}\sqcup\overline{W}_{1}$ is a basis for
$A_{1}=\mathcal{U}_{1}\oplus\tilde{A}_{1}$, satisfying conditions (I) and
(II).

Then assume that $p>1$ and we have obtained all $V_{k}$, $W_{k}$ and
$\overline{W}_{k}$ for $p>k\geq 1$. Also, $W_{p}$ generates $\mathcal{U}_{p}$
and $\tilde{V}_{p}$ generates $\tilde{A}_{p}$ while $W_{p}\sqcup\tilde{V}_{p}$
being a basis for $A_{p}=\mathcal{U}_{p}\oplus\tilde{A}_{p}$. Then it suffices
to obtain $V_{p}$ and $\overline{W}_{p}$ from $\tilde{V}_{p}$. By applying
Lemma 2.5, the chain complex

${\cdots}$${A_{p+1}}$${\tilde{A}_{p}}$${0}$$\scriptstyle{d_{p+1}}$$\scriptstyle{d_{p}}$

decomposes into

${\cdots}$${\tilde{A}_{p+1}}$${0}$${0}$${\mathcal{U}_{p+1}}$${\overline{\mathcal{U}}_{p}}$${0}$${0}$${F_{p}}$${0}$$\scriptstyle{d_{p+2}}$$\scriptstyle{d_{p+1}}$${\bigoplus}$${\bigoplus}$

where $\tilde{A}_{p+1}$, $\mathcal{U}_{p+1}$, $\overline{\mathcal{U}}_{p}$ and
$F_{p}$ are the submodules generated by sets $\tilde{V}_{p+1}$, $W_{p+1}$,
$\overline{W}_{p}$ and $R_{p}$ respectively. Note that $\tilde{V}_{p+1}\sqcup
W_{p+1}$ is a basis for $A_{p+1}=\tilde{A}_{p+1}\oplus\mathcal{U}_{p+1}$ and
$\overline{W}_{p}\sqcup R_{p}$ is a basis for
$\tilde{A}_{q}=\overline{\mathcal{U}}_{p}\oplus F_{p}$. Since $d_{p}$ maps
$\tilde{A}_{p}$ to $0$, we assign $V_{p}=R_{p}$ satisfying condition (I).
Hence we have obtained $V_{p}\sqcup W_{p}\sqcup\overline{W}_{p}$ as a basis
for $A_{p}=\mathcal{U}_{p}\oplus\tilde{A}_{p}$, satisfying conditions (I) and
(II).

For the downward branch, we first apply Lemma 2.5 to

${0}$${\tilde{A}_{0}}$${A_{-1}}$${\cdots}$$\scriptstyle{d_{0}}$$\scriptstyle{d_{-1}}$

It decomposes into

${0}$${F_{0}}$${0}$${0}$${\mathcal{U}_{0}}$${\overline{\mathcal{U}}_{-1}}$${0}$${0}$${\tilde{A}_{-1}}$${\cdots}$$\scriptstyle{d_{0}}$${\bigoplus}$$\scriptstyle{d_{-1}}$${\bigoplus}$

where $F_{0}$, $\mathcal{U}_{0}$, $\overline{\mathcal{U}}_{-1}$ and
$\tilde{A}_{-1}$ are the submodules generated by sets $V_{0}$, $W_{0}$,
$\overline{W}_{-1}$ and $R_{-1}$ respectively. Note that $V_{0}\sqcup W_{0}$
is a basis for $\tilde{A}_{0}=F_{0}\oplus\mathcal{U}_{0}$ and
$\overline{W}_{-1}\sqcup R_{-1}$ is a basis for
$A_{-1}=\overline{\mathcal{U}}_{-1}\oplus\tilde{A}_{-1}$. Recall that
$\overline{W}_{0}$ is obtained at the beginning of the proof, thus now we have
obtained all $V_{0}$, $W_{0}$ and $\overline{W}_{0}$. Since $\overline{W}_{0}$
generates $\overline{\mathcal{U}}_{0}$ and $V_{0}\sqcup W_{0}$ is a basis for
$\tilde{A}_{0}$, $V_{0}\sqcup W_{0}\sqcup\overline{W}_{0}$ is a basis for
$A_{0}=\overline{\mathcal{U}}_{0}\oplus\tilde{A}_{0}$, satisfying conditions
(I) and (II).

Then assume that $q<0$ and we have obtained all $V_{k}$, $W_{k}$ and
$\overline{W}_{k}$ for $0\leq k<q$. Also, $\overline{W}_{q}$ generates
$\overline{\mathcal{U}}_{q}$ and $R_{q}$ generates $\tilde{A}_{q}$ while
$\overline{W}_{q}\sqcup R_{q}$ being a basis for
$A_{q}=\overline{\mathcal{U}}_{q}\oplus\tilde{A}_{q}$. Then it suffices to
obtain $V_{q}$ and $W_{q}$ from $R_{q}$. By applying Lemma 2.5, the chain
complex

${0}$${\tilde{A}_{q}}$${A_{q-1}}$${\cdots}$$\scriptstyle{d_{q}}$$\scriptstyle{d_{q-1}}$

decomposes into

${0}$${F_{q}}$${0}$${0}$${\mathcal{U}_{q}}$${\overline{\mathcal{U}}_{q-1}}$${0}$${0}$${\tilde{A}_{q-1}}$${\cdots}$$\scriptstyle{d_{q}}$${\bigoplus}$$\scriptstyle{d_{q-1}}$${\bigoplus}$

where $F_{q}$, $\mathcal{U}_{q}$, $\overline{\mathcal{U}}_{q-1}$ and
$\tilde{A}_{q-1}$ are the submodules generated by sets $V_{q}$, $W_{q}$,
$\overline{W}_{q-1}$ and $R_{q-1}$ respectively. Note that $V_{q}\sqcup W_{q}$
is a basis for $\tilde{A}_{q}=F_{q}\oplus\mathcal{U}_{q}$ and
$\overline{W}_{q-1}\sqcup R_{q-1}$ is a basis for
$A_{q-1}=\overline{\mathcal{U}}_{q-1}\oplus\tilde{A}_{q-1}$. Hence we have
obtained $V_{q}\sqcup W_{q}\sqcup\overline{W}_{q}$ as a basis for
$A_{q}=\overline{U}_{q}\oplus\tilde{A}_{q}$, satisfying conditions (I) and
(II).

In conclusion, we have obtained $V_{n}\sqcup W_{n}\sqcup\overline{W}_{n}$ be a
homogeneous basis of $A_{n}$ satisfying condition (I) and (II) for each $n$. ∎

######  Corollary 2.7.

The chain complex $(A,d)$ in Proposition 2.6 is homotopic to the direct sum of
chain complexes of the Types (1) and (2) given in Definition 1.3. Each $v\in
V_{n}$ generates a component $U_{n,\deg v,\infty}$. Each pair $w\in W_{n+1}$
and $\bar{w}\in\overline{W}_{n}$ generate a component
$U_{n,\deg\bar{w},m_{w}}$ where $d(w)=x^{m_{w}}\bar{w}$ for some positive
integer $m_{w}$ depending on $w$.

Recall that $\mathbb{Z}_{+,\infty}=\mathbb{Z}_{+}\cup\\{+\infty\\}$. Then for
each $n$, there exist $K_{n}\in\mathbb{Z}_{+,\infty}$ and the sequence
$\\{(s_{n}(i),m_{n}(i))\\}_{i=1}^{K_{n}}\subseteq\mathbb{Z}\times\mathbb{Z}_{+,\infty}$
satisfies $s_{n}(i)\leq s_{n}(i+1)$ and $m_{n}(i)\leq m_{n}(i+1)$ if
$s_{n}(i)=s_{n}(i+1)$, such that

$A\simeq\bigoplus_{n=-\infty}^{\infty}\bigoplus_{i=1}^{K_{n}}U_{n,s_{n}(i),m_{n}(i)}.$

Consequently,

$H(A)\cong\bigoplus_{n=-\infty}^{\infty}\bigoplus_{i=1}^{K_{n}}H(U_{n,s_{n}(i),m_{n}(i)})$

where $H(U_{n,s,\infty})\cong\mathbb{F}[x]||n||\\{s\\}$ and
$H(U_{n,s,m})\cong\mathbb{F}[x]/(x^{m})||n||\\{s\\}$.

###### Proof.

Let $V_{n}\sqcup W_{n}\sqcup\overline{W}_{n}$ be the basis of $A_{n}$ from
Proposition 2.6. Note that each $v\in V_{n}$ generates a subcomplex
$U_{n,s,\infty}$ and each pair of $(w,\bar{w})\in W_{n+1}\times W_{n}$
generate a subcomplex $U_{n,s,m}$. So it suffices to show that

$U_{n,s,0}\ =\
0\to\mathbb{F}[x]||n+1||\\{s\\}\xrightarrow{1}\mathbb{F}[x]||n||\\{s\\}\to 0$

is homotopic to zero. Consider the identity map $id$ and the chain homotopy
given by $h=1\cdot$ in the diagram

${0}$${\mathbb{F}[x]}$${\mathbb{F}[x]}$${0}$${0}$${\mathbb{F}[x]}$${\mathbb{F}[x]}$${0}$$\scriptstyle{1}$$\scriptstyle{0}$$\scriptstyle{1}$$\scriptstyle{id}$$\scriptstyle{1}$$\scriptstyle{id}$$\scriptstyle{0}$

Here $h\circ d+d\circ h=id$. Hence $id$ is null-homotopic and

$U_{n,s,0}\ =\
0\to\mathbb{F}[x]||n+1||\\{s\\}\xrightarrow{1}\mathbb{F}[x]||n||\\{s\\}\to 0$

is homotopic to zero when. ∎

###  2.3. Uniqueness of the decomposition

The following lemma is a generalization of [8, Lemma 4.14].

######  Lemma 2.8.

Recall that $\mathbb{Z}_{+,\infty}=\mathbb{Z}_{+}\cup\\{+\infty\\}$. Let
$K,K^{\prime}\in\mathbb{Z}_{+,\infty}$ and $n\in\mathbb{Z}$. Suppose there are
two sequences $\\{(s(i),m(i))\\}_{i=1}^{K}$ and
$\\{(s^{\prime}(i),m^{\prime}(i))\\}_{i=1}^{K^{\prime}}$ in
$\mathbb{Z}\times\mathbb{Z}_{+,\infty}$ satisfying:

  * •

If $i<j$, then $s(i)\leq s(j)$ and $s^{\prime}(i)\leq s^{\prime}(j)$.

  * •

If $i<j$ and $s(i)=s(j)$, then $m(i)\leq m(j)$.

  * •

If $i<j$ and $s^{\prime}(i)=s^{\prime}(j)$, then $m^{\prime}(i)\leq
m^{\prime}(j)$.

  * •

For every $s\in\mathbb{Z}$, index sets $\\{i\ |\ s(i)=s\\}$ and $\\{i\ |\
s^{\prime}(i)=s\\}$ are finite.

If

$\bigoplus_{i=1}^{K}H(U_{n,s(i),m(i)})\cong\bigoplus_{j=1}^{K^{\prime}}H(U_{n,s^{\prime}(j),m^{\prime}(j)})$

as graded $\mathbb{F}[x]$-modules, then $K=K^{\prime}$ and
$s(i)=s^{\prime}(i),m(i)=m^{\prime}(i)$ for every $1\leq i\leq K$.

###### Proof.

For a graded $\mathbb{F}$-space $V=\bigoplus_{i\in\mathbb{Z}}V_{i}$, we
consider its graded dimension as the Hilbert series, that is,
$\mathrm{gdim}_{\mathbb{F}}V:=\sum_{i\in\mathbb{Z}}(\dim_{\mathbb{F}}V_{i})t^{i}$.
Denote

$M:=\bigoplus_{i=1}^{K}H(U_{n,s(i),m(i)})\cong\bigoplus_{j=1}^{K^{\prime}}H(U_{n,s^{\prime}(j),m^{\prime}(j)}).$

From Corollary 2.7, we have
$H(U_{n,s(i),\infty})\cong\mathbb{F}[x]||n||\\{s(i)\\}$ and
$H(U_{n,s(i),m(i)})\cong\mathbb{F}[x]/(x^{m(i)})||n||\\{s(i)\\}$ for
$m(i)<\infty$. Then graded dimension is well-defined on $M$ since the
$\mathbb{F}[x]$-grading on $M$ is bounded below and for each fixed
$s\in\mathbb{Z}$ the index set is finite.

Let $w_{i}$ be the generator of $H(U_{n,s(i),m(i)})$ which is homogeneous of
degree $s(i)$. For any $l\geq 0$, define $M^{(l)}=x^{l}M/x^{l+1}M$. Then
$M^{(l)}$ is an $\mathbb{F}$-space with homogeneous basis
$\\{x^{l}w_{i}\\}_{i\in I_{l}}$. Here $\\{(s(i),m(i))\\}_{i\in I_{l}}$ is a
subsequence of $\\{(s(i),m(i))\\}_{i=1}^{K}$ depending on the choice of $l$,
where $m(i)>l$ for all $i\in I_{l}$ in the subsequence. Consider the graded
dimension of $M^{(l)}$. Then
$\mathrm{gdim}_{\mathbb{F}}M^{(l)}=t^{l}\sum_{i\in I_{l}}t^{s(i)}=\sum_{i\in
I_{l}}t^{s(i)+l}$. Define $S_{c,l}:=\\{i\in\mathbb{Z}\ |\ s(i)=c,\ m(i)>l\\}$
and similarly $S^{\prime}_{c,l}:=\\{i\in\mathbb{Z}\ |\ s^{\prime}(i)=c,\
m^{\prime}(i)>l\\}$. Then $S_{c,l}\subset I_{l}$ and the cardinality of
$S_{c,l}$ is the coefficient of the $t^{c+l}$ term in
$\mathrm{gdim}_{\mathbb{F}}M^{(l)}$. Therefore each $S_{c,l}$ is finite
according to locally finiteness and this coefficient of the $t^{c+l}$ in
$\mathrm{gdim}_{\mathbb{F}}M^{(l)}$ is also the cardinality of
$S^{\prime}_{c,l}$. Thus $S_{c,l}$ and $S^{\prime}_{c,l}$ have the same
(finite) cardinality for each $c$ and $l$. Hence the lemma follows. ∎

We are now ready to prove Theorem 1.4.

###### Proof of Theorem 1.4.

The $\mathbb{F}[x]$-grading of $PC_{n}$ is bounded below since the filtration
of $C_{n}$ is bounded below, and $PC$ is locally finite dimensional since
$(C,\mathcal{F})$ is locally finite dimensional. Therefore $(PC,d_{x})$
satisfies all the conditions in Proposition 2.6. The existence of
Decompositions (3) and (4) follows from Corollary 2.7. Since $PC$ is locally
finite dimensional, we know that $\\{i\ |\ s(i)=s\\}$ is finite for all
$s\in\mathbb{Z}$ in the decomposition (4). Thus, Lemma 2.8 implies that
Decompositions (3) and (4) are unique up to chain homotopy and permutation of
factors. ∎

##  3\. Spectral Sequences

There are several approaches to compute the spectral sequence of filtered
chain complexes. We will use exact couples to compute the spectral sequence of
summands $U_{n,s,m}$ and $U_{n,s,\infty}$. Properties of exact couples can be
found in many books such as [4] and [6]. Let us first briefly review this
approach.

######  Definition 3.1.

[4] An exact couple $\mathcal{C}=(A,E,f,g,h)$ consists of two graded
$\mathbb{F}$-linear spaces $A$, $E$ and homogeneous homomorphisms $f$, $g$ and
$h$ where the following diagram

${A}$${A}$${E}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{h}$

is exact. The differential map $d$ on $E$ is defined to be $d=g\circ h$.

The derived exact couple
$\mathcal{C}^{\prime}=(A,E,f,g,h)^{\prime}=(A^{\prime},E^{\prime},f^{\prime},g^{\prime},h^{\prime})$
is defined by

  * •

$A^{\prime}=f(A)$,

  * •

$E^{\prime}=\mathrm{ker}~{}d/\mathrm{im}~{}d=H(E,d)$,

  * •

$f^{\prime}=f|_{A^{\prime}}$,

  * •

$g^{\prime}(f(a))=g(a)+d(E)$ for any $a\in A$,

  * •

$h^{\prime}(b+d(E))=h(b)$ for any $b\in\mathrm{ker}~{}d$.

######  Definition 3.2.

[8] For a graded chain complex $K$ of free $\mathbb{F}[x]$-modules, the short
exact sequence $0\to K\\{1\\}\xrightarrow{x}K\xrightarrow{\pi_{x}}K/xK\to 0$
where $\pi_{x}$ is the standard quotient map. It induces an exact couple
$\mathcal{H}^{(1)}(K)=(A^{(1)},E^{(1)},f^{(1)},g^{(1)},h^{(1)})$ given by

${H(K)}$${H(K)}$${H(K/xK)}$$\scriptstyle{x}$$\scriptstyle{(\pi_{x})_{*}}$$\scriptstyle{\Delta}$

Denote by $\mathcal{H}^{(r)}(K)$ the exact couple of $\mathcal{H}^{(1)}(K)$
derived $(r-1)$ times.

######  Lemma 3.3.

[8] As graded $\mathbb{F}$-linear spaces,

$\displaystyle E^{(r)}(U_{n,s,\infty})$
$\displaystyle~{}~{}~{}~{}\cong~{}~{}~{}~{}\mathbb{F}||n||\\{s\\}~{}~{}~{}~{}~{}\forall
r\geq 1,$ $\displaystyle E^{(r)}(U_{n,s,m})$
$\displaystyle~{}~{}~{}~{}\cong~{}~{}~{}~{}\left\\{\begin{array}[]{lc}\mathbb{F}||n+1||\\{s+m\\}\oplus\mathbb{F}||n||\\{s\\}&1\leq
r\leq m,\\\ 0&r>m.\end{array}\right.$

In particular, $E^{(\infty)}(U_{n,s,\infty})\cong E^{(1)}(U_{n,s,\infty})$ and
$E^{(\infty)}(U_{n,s,m})\cong E^{(m+1)}(U_{n,s,m})$.

###### Proof.

(Following [8, Lemma 4.17].) First consider $\mathcal{H}(U_{n,s,\infty})$.
Since the only nonzero term of $U_{n,s,\infty}$ is located at the $n$-th
homological degree, the connecting homomorphism $\Delta=h^{(1)}$ is always
zero. Thus $d^{(r)}=0$ on $E^{(r)}$ for all $r\geq 1$. Therefore $E^{(r)}\cong
E^{(1)}\cong\mathbb{F}[x]/x\mathbb{F}[x]||n||\\{s\\}\cong\mathbb{F}||n||\\{s\\}$
for all $r\geq 1$.

Next consider $\mathcal{H}(U_{n,s,m})$. For $1\leq r<m$,
$x^{r}\cdot\mathbb{F}[x]/(x^{m})=\mathrm{Span}\\{x^{r},x^{r+1},\ldots,x^{m-1}\\}$
is a subspace of $\mathbb{F}[x]/(x^{m})$. Define the $\mathbb{F}$-linear
mapping $x^{-r}$ by

$x^{-r}:~{}~{}~{}x^{r}\cdot\mathbb{F}[x]/(x^{m})\to\mathbb{F}[x]/(x^{m}),~{}~{}~{}~{}x^{r+i}\mapsto
x^{i}~{}~{}~{}0\leq i\leq m-r-1.$

We will show by induction that for all $1\leq r\leq m$:

$\mathcal{H}^{(r)}(U_{n,s,m})\cong(x^{r-1}\cdot
H(U_{n,s,m}),H(U_{n,s,m}/xU_{n,s,m}),x,\pi_{x}\circ x^{1-r},x^{m-1}).$

For $r=1$, we have

$A^{(1)}=H(U_{n,s,m})\cong\mathbb{F}[x]/(x^{m})||n||\\{s\\}$

and

$E^{(1)}=H(U_{n,s,m}/xU_{n,s,m})\cong\mathbb{F}||n+1||\\{s+m\\}\oplus\mathbb{F}||n||\\{s\\}.$

The nonzero part of $\mathcal{H}^{(1)}(U_{n,s,m})$ is the following part:

${U_{n,s,m}\\{1\\}}$${U_{n,s,m}}$${U_{n,s,m}/xU_{n,s,m}}$${0}$${\mathbb{F}\\{s+m\\}}$${{||n+1||}}$${\mathbb{F}[x]/(x^{m})\\{s+1\\}}$${\mathbb{F}[x]/(x^{m})\\{s\\}}$${\mathbb{F}\\{s\\}}$${{||n||}}$${0}$${{||n-1||}}$$\scriptstyle{x}$$\scriptstyle{\Delta}$$\scriptstyle{\pi_{x}}$

where $\Delta(1)=x^{m-1}$. Thus
$\mathcal{H}^{(1)}(U_{n,s,m})=(H(U_{n,s,m}),H(U_{n,s,m}/xU_{n,s,m}),x,\pi_{x},\Delta)$.

Assume the inductive hypothesis for $r\leq k-1<m$, and compute
$\mathcal{H}^{(k)}(U_{n,s,m})$ by considering the derived exact couple
$(x^{k-2}\cdot H(U_{n,s,m}),H(U_{n,s,m}/xU_{n,s,m}),x,\pi_{x}\circ
x^{2-k},x^{m-1})^{\prime}$. Then $A^{(k)}=x\cdot A^{(k-1)}\cong x^{k-1}\cdot
H(U_{n,s,m})$. From the diagram above we may still find that $f^{(k)}=x$ and
$h^{(k)}=\Delta=x^{m-1}$. For any $\alpha\in A^{(k-1)}$, we have

$g^{(k-1)}(\alpha)=\pi_{x}\circ x^{2-k}(\alpha)=\pi_{x}\circ
x^{1-k}(x\alpha)=(\pi_{x}\circ x^{1-k})(f^{(k-1)}(\alpha)).$

Therefore $g^{(k)}(\alpha)=\pi_{x}\circ x^{1-k}(\alpha)$. Note that
$d^{(k-1)}=g^{(k-1)}\circ h^{(k-1)}=(\pi_{x}\circ x^{2-k})\circ
x^{m-1}=\pi_{x}\circ x^{m-k+1}=0$, thus $E^{(k)}\cong E^{(k-1)}\cong
H(U_{n,s,m}/xU_{n,s,m})\cong\mathbb{F}||n+1||\\{s+m\\}\oplus\mathbb{F}||n||\\{s\\}$.

Finally consider $r=m+1$. The differential map $d^{(m)}$ becomes
$d^{(m)}=g^{(m)}\circ h^{(m)}=(\pi_{x}\circ x^{1-m})\circ x^{m-1}=\pi_{x}\circ
1=i$ which is an isomorphism on
$\mathbb{F}||n+1||\\{s+m\\}\oplus\mathbb{F}||n||\\{s\\}$, then
$E^{(m+1)}=H(E^{(m)},i)\cong 0$. Hence $E^{(r)}\cong E^{(m+1)}\cong 0$ for all
$r>m$. ∎

Under our assumptions, the spectral sequence $\\{E^{(r)}\\}$ does not
necessarily collapse in the usual sense. However, from Lemma 3.3, each
$E^{(r)}(U_{n,s,\infty})$ and $E^{(r)}(U_{n,s,m})$ both collapse after finite
pages. Therefore, we have the following corollary.

######  Corollary 3.4.

Let $\\{E^{(r)}\\}$ be the spectral sequence in Theorem 1.5. Then
$\\{E^{(r)}\\}$ collapses locally to $E^{(\infty)}$, which means
$\\{E_{n,s}^{(r)}\\}$ collapses to $E_{n,s}^{(\infty)}$ for every
$(n,s)\in\mathbb{Z}\times\mathbb{Z}$.

We have another observation from Lemma 3.3.

######  Corollary 3.5.

Let $K$ be a chain complex of free graded $\mathbb{F}[x]$-module satisfying:

  * •

Its differential $d$ is homogeneous and preserves the $\mathbb{F}[x]$-grading
of $K$;

  * •

For each $n$, the $\mathbb{F}[x]$-grading of $K_{n}$ is bounded below;

  * •

For each $n$, $K_{n}$ is locally finite dimensional over $\mathbb{F}$.

Then we have that

$E^{(1)}(K)\cong H(K/xK)$

and that $\\{E^{(r)}(K)\\}$ collapses locally to $E^{(\infty)}(K)$ where

$E^{(\infty)}(K)\cong H(K/(x-1)K).$

In particular, assume that $K$ is the persistent chain complex of a filtered
chain complex $(C,d,\mathcal{F})$ over $\mathbb{F}$ satisfying:

  * (a)

For each $n$, the filtration $\mathcal{F}$ on $C_{n}$ is bounded below;

  * (b)

$(C,d,\mathcal{F})$ is locally finite dimensional over $\mathbb{F}$.

Then $K/xK$ is isomorphic to the graded chain complex associated to
$(C,d,\mathcal{F})$, and $K/(x-1)K$ is isomorphic to the filtered chain
complex $(C,d,\mathcal{F})$.

###### Proof.

From Definitions 3.1 and 3.2, we have that $E^{(1)}(K)\cong H(K/xK)$. Since
$K$ satisfies all conditions in Proposition 2.6, it admits the decomposition
in Corollary 2.7. It remains to show that

$E^{(\infty)}(U_{n,s,\infty})\cong H(U_{n,s,\infty}/(x-1)U_{n,s,\infty})$

and

$E^{(\infty)}(U_{n,s,m})\cong H(U_{n,s,m}/(x-1)U_{n,s,m}),$

where $U_{n,s,\infty}$ and $U_{n,s,m}$ are given in Definition 1.3. From ring
isomorphism $\mathbb{F}[x]/(x-1)\cong\mathbb{F}$, we have

$U_{n,s,\infty}/(x-1)U_{n,s,\infty}\cong 0\to\mathbb{F}||n||\\{s\\}\to 0$

and

$U_{n,s,m}/(x-1)U_{n,s,m}\cong
0\to\mathbb{F}||n+1||\\{s+m\\}\xrightarrow{1}\mathbb{F}||n||\\{s\\}\to 0.$

Hence $H(U_{n,s,\infty}/(x-1)U_{n,s,\infty})\cong\mathbb{F}||n||\\{s\\}$ and
$H(U_{n,s,m}/(x-1)U_{n,s,m})\cong 0$. Comparing these to Lemma 3.3, we know
that $E^{(\infty)}(K)\cong H(K/(x-1)K)$.

Let $K$ be the persistent chain complex of a filtered chain complex
$(C,d,\mathcal{F})$ over $\mathbb{F}$ satisfying conditions (a) and (b). From
Definition 1.1, recall that $x$ is a homogeneous element of degree $1$ that
act on $K$ as the natural inclusion map
$i^{p}:\mathcal{F}^{p}C\hookrightarrow\mathcal{F}^{p+1}C$ for each
$p\in\mathbb{Z}$. Fix $p\in\mathbb{Z}$, we have
$x(\mathcal{F}^{p-1}C)\subset\mathcal{F}^{p}C$. Thus

$K/xK\cong\bigoplus_{p\in\mathbb{Z}}\mathcal{F}^{p}C/\mathcal{F}^{p-1}C.$

From Definition 2.1 and Proposition 2.2, following their notations, we have
the differential map $d_{x}$ of $K$ is given by $(d_{x})_{n}^{p}=\sum_{q\leq
p}x^{p-q}d_{n}^{p,q}$. Then $d_{x}$ induces a differential map $d_{0*}$ in
$K/xK$ given by

$\bigl{(}d_{0*}\bigr{)}_{n}^{p}=d_{n}^{p,p}=\pi_{n-1}^{p,p}\circ d_{n}^{p},$

where $\pi_{n-1}^{p,p}\circ d_{n}^{p}:G_{n}^{p}\to G_{n-1}^{p}$ is the
restriction of the differential map $d$ on these $\mathbb{F}$-spaces. Since
each $\mathbb{F}$-space $G_{n}^{p}$ is fixed by
$\mathcal{F}^{p}C_{n}=\mathcal{F}^{p-1}C_{n}\oplus G_{n}^{p}$, we have
$G_{n}^{p}\cong\mathcal{F}^{p}C_{n}/\mathcal{F}^{p-1}C_{n}$. Therefore $K/xK$
is isomorphic to the associated graded chain complex of $C$.

Notice that $x=1$ in the quotient chain complex $K/(x-1)K$. We know that the
image of the homogeneous component of degree $p$ on homological degree $n$
under quotient map is

$\Bigl{(}K/(x-1)K\Bigl{)}_{n}^{p}=\bigoplus_{k\geq
0}1^{k}G_{n}^{p-k}=\bigoplus_{q=-\infty}^{p}G_{n}^{q}=\mathcal{F}^{p}C_{n}.$

Let $d_{1*}$ be the induced differential map of $K/(x-1)K$, then by Definition
2.1 we have

$\bigl{(}d_{1*}\bigr{)}_{n}^{p}=\sum_{q\leq p}1^{p-q}d_{n}^{p,q}=d_{n}^{p}$

where $d_{n}^{p}$ is the differential map $d_{n}:C_{n}\to C_{n-1}$ of
$(C,d,\mathcal{F})$ restricted on $G_{n}^{p}$. Thus $K/(x-1)K$ is isomorphic
to the filtered chain complex $(C,d,\mathcal{F})$. ∎

Now we prove Theorem 1.5.

###### Proof of Theorem 1.5.

The decomposition follows from Theorem 1.4. The structures of
$E^{(r)}(U_{n,s,m})$ and $E^{(r)}(U_{n,s,\infty})$ are given in Lemma 3.3. By
Corollary 3.4, $\\{E^{(r)}\\}$ collapses locally. ∎

##  4\. Relations Between $E^{(r)}$ and $PH$

Next, we establish the relation between the spectral sequence and the
persistent homology. From the discussions in the above sections, we know that
as $\mathbb{F}$-spaces, the spectral sequence is determined by the persistent
chain complex. Thus, it is straight forward to give a formula of the
$\mathbb{F}$-dimension of the spectral sequence by counting the relevant
components in the persistent homology. Moreover, we will further show in this
section that the persistent homology can also be recovered from the spectral
sequence if the filtration is bounded below uniformly.

######  Corollary 4.1.

Recall that $\mu_{n}^{i,j}$ is the persistent multiplicities from [2, VII.1]
for finite filtered chain complex, and $\nu_{n,s,n}$ be defined in Definition
1.7. Then

  * •

$\mu_{n}^{i,j}=\nu_{n,i,j-i}$,

  * •

$\nu_{n,s,m}=\mu_{n}^{s,s+m}$.

Also, the persistent Betti number $b_{n}^{i,j}$ defined in [2, VII.1] can be
expressed in terms of $\nu_{n,s,m}$ as

$b_{n}^{i,j}=\sum_{j-m<s\leq i}\nu_{n,s,m}.$

###### Proof.

This follows directly from Definition 1.7 with an index changing. The
multiplicity $\nu_{n,s,m}$ of $H(U_{n,s,m})$ means the number of $n$-homology
cycles generating at filtration level $s$ and surviving for $m$ filtration
levels. By [2, VII.1], the persistent multiplicity $\mu_{n}^{i,j}$ means
numbers of $n$-homology cycles generating at filtration level $i$ while
getting killed at filtration level $j$. Hence $\mu_{n}^{i,j}=\nu_{n,i,j-i}$
and $\nu_{n,s,m}=\mu_{n}^{s,s+m}$. Following the fundamental lemma of
persistent homology from [2, VII.1], we have $b_{n}^{i,j}=\sum_{s\leq
i}\sum_{k>j}\mu_{n}^{s,k}$. Therefore

$b_{n}^{i,j}=\sum_{s\leq i}\sum_{k>j}\nu_{n,s,k-s}=\sum_{s\leq
i}\sum_{m+s>j}\nu_{n,s,m}=\sum_{j-m<s\leq i}\nu_{n,s,m}.$

∎

Recall that $E_{n,s}^{(r)}$ is the homogeneous component of $E^{(r)}$ with
homological grading $n$ and $\mathbb{F}[x]$-module grading $s$. Then we have
the following proposition.

######  Proposition 4.2.

For any $r>0$,

$\dim_{\mathbb{F}}E_{n,s}^{(r)}=\nu_{n,s,\infty}+\sum_{m\geq
r}(\nu_{n,s,m}+\nu_{n-1,s-m,m}).$

###### Proof.

From Theorem 1.5, the spectral sequence decomposes uniquely as
$E^{(r)}\cong\bigoplus_{l=-\infty}^{\infty}\bigoplus_{i=1}^{K_{l}}E^{(r)}(U_{l,s_{l}(i),m_{l}(i)})$.
Consider an extended sequence
$\\{(l,s_{l}(i),m_{l}(i))\\}\subseteq\mathbb{Z}\times\mathbb{Z}\times\mathbb{Z}_{+,\infty}$
and its subsequence $\\{(l,s_{l}(i),m_{l}(i))\\}_{(l,i)\in I_{n,s}}$ where

$I_{n,s}:=\\{(l,i)\in\mathbb{Z}\times\mathbb{Z}_{+,\infty}\ |\ 1\leq i\leq
K_{l},\ \mathbb{F}||n||\\{s\\}\subseteq E^{(r)}(U_{l,s_{l}(i),m_{l}(i)})\\}.$

Then $E^{(r)}_{n,s}\cong\bigoplus_{(l,i)\in I_{n,s}}\mathbb{F}||n||\\{s\\}$
since each $E^{(r)}(U_{l,s_{l}(i),m_{l}(i)})$ contributes at most one summand
of $\mathbb{F}||n||\\{s\\}$ in $E^{(r)}_{n,s}$ from Lemma 3.3. Thus

$\dim_{\mathbb{F}}E^{(r)}_{n,s}=\dim_{\mathbb{F}}\mathbb{F}^{\oplus|I_{n,s}|}=|I_{n,s}|.$

It suffices to count $|I_{n,s}|$ in terms of $\nu$.

We first separate $I_{n,s}=I_{n,s,\infty}\sqcup I^{\prime}_{n,s}$ where
$I_{n,s,\infty}:=\\{(n,i)\ |\ 1\leq i\leq K_{n},\ s_{n}(i)=s,\
m_{n}(i)=\infty\\}$ and $I^{\prime}_{n,s}:=I_{n,s}\backslash I_{n,s,\infty}$,
because we have $E^{(r)}(U_{n,s,\infty})\cong\mathbb{F}||n||\\{s\\}$ for all
$r\geq 1$ in Lemma 3.3. Notice that $\nu_{n,s,\infty}=|I_{n,s,\infty}|$.

Next consider $I^{\prime}_{n,s}$. According to Lemma 3.3,
$E^{(r)}(U_{l,s,m})\cong 0$ for all $m<r$. Also, any rest of the summand
$\mathbb{F}||n||\\{s\\}$ in $E_{n,s}^{(r)}$ coming from either
$E^{(r)}(U_{n,s,m})\cong\mathbb{F}||n+1||\\{s+m\\}\oplus\mathbb{F}||n||\\{s\\}$
or
$E^{(r)}(U_{n-1,s-m,m})\cong\mathbb{F}||n||\\{s\\}\oplus\mathbb{F}||n-1||\\{s-m\\}$
for all $m\geq r$. Therefore $I^{\prime}_{n,s}=I_{n,s,m\geq r}\sqcup
I_{n-1,s-m,m\geq r}$ where

$I_{n,s,m\geq r}:=\\{(n,i)\ |\ 1\leq i\leq K_{n},\ s_{n}(i)=s,\ m_{n}(i)\geq
r\\}$

and

$I_{n-1,s-m,m\geq r}:=\\{(n-1,i)\ |\ 1\leq i\leq K_{n-1},\
s_{n}(i)=s-m_{n}(i),\ m_{n}(i)\geq r\\}.$

Thus $|I_{n,s,m\geq r}|=\sum_{m\geq r}\nu_{n,s,m}$ and $|I_{n-1,s-m,m\geq
r}|=\sum_{m\geq r}\nu_{n-1,s-m,m}$. It is clear that $I_{n,s,m\geq r}\cap
I_{n-1,s-m,m\geq r}=\emptyset$ since the index of $I_{n,s,m\geq r}$ coming
form homological degree $n$ while the other coming from homological degree
$n-1$. Hence

$|I_{n,s}|=|I_{n,s,\infty}|+|I_{n,s,m\geq r}|+|I_{n-1,s-m,m\geq
r}|=\nu_{n,s,\infty}+\sum_{m\geq r}(\nu_{n,s,m}+\nu_{n-1,s-m,m}).$

∎

Now we prove Theorem 1.8.

###### Proof of Theorem 1.8.

The first part of the theorem follows from Proposition 4.2. If $\\{E^{(r)}\\}$
is the spectral sequence of the persistent chain complex $(PC,d_{x})$
satisfying conditions in Theorem 1.4, it suffices to show that

  * •

$\nu_{n,s,\infty}=\dim_{\mathbb{F}}E_{n,s}^{(\infty)}$ and

  * •

$\nu_{n,s,m}=\dim_{\mathbb{F}}E_{n,s}^{(m)}-\dim_{\mathbb{F}}E_{n,s}^{(m+1)}-\nu_{n-1,s-m,m}$.

From Corollary 3.4, $\\{E^{(r)}\\}$ collapses locally to $E^{(\infty)}$. Thus
$E_{n,s}^{(\infty)}$ exists for every $n,s\in\mathbb{Z}$ and is also finite
$\mathbb{F}$-dimensional. It consists of the free part of the homology group
with homogeneous grading. Suppose $E_{n,s}^{(r)}$ collapses at the $M$-th
page, which means $E_{n,s}^{(r)}\cong E_{n,s}^{(r+1)}\cong E_{n,s}^{(\infty)}$
for all $r\geq M$ but $E_{n,s}^{(M-1)}\not\cong E_{n,s}^{(M)}$. Consider
$\dim_{\mathbb{F}}E_{n,s}^{(r)}=\nu_{n,s,\infty}+\sum_{m\geq
r}(\nu_{n,s,m}+\nu_{n-1,s-m,m})$ from Proposition 4.2. For all $r\geq M$, by
$E_{n,s}^{(r)}\cong E_{n,s}^{(r+1)}$ we have

$\nu_{n,s,r}+\nu_{n-1,s-m,r}=\dim_{\mathbb{F}}E_{n,s}^{(r)}-\dim_{\mathbb{F}}E_{n,s}^{(r+1)}=0.$

Thus $\sum_{m\geq M}(\nu_{n,s,m}+\nu_{n-1,s-m,m})=0$ and
$\dim_{\mathbb{F}}E_{n,s}^{(\infty)}=\dim_{\mathbb{F}}E_{n,s}^{(M)}=\nu_{n,s,\infty}$.
Hence $\nu_{n,s,\infty}$ is determined by the infinite page
$E_{n,s}^{(\infty)}$.

For general $\nu_{n,s,m}$, consider Proposition 4.2 again. We have

$\dim_{\mathbb{F}}E_{n,s}^{(m)}-\dim_{\mathbb{F}}E_{n,s}^{(m+1)}=\nu_{n,s,m}+\nu_{n-1,s-m,m}.$

Thus
$\nu_{n,s,m}=\dim_{\mathbb{F}}E_{n,s}^{(m)}-\dim_{\mathbb{F}}E_{n,s}^{(m+1)}-\nu_{n-1,s-m,m}$.

If the filtration of $(C,d,\mathcal{F})$ is bounded below uniformly, the
$\mathbb{F}[x]$-grading of $(PC,d_{x})$ is therefore bounded below uniformly.
Then there exists $S\in\mathbb{Z}$, such that $\nu_{n,s,m}=0$ for all
$n\in\mathbb{Z}$, $m\in\mathbb{Z}_{+,\infty}$ and $s<S$. Thus all
$\nu_{n,S,m}=\dim_{\mathbb{F}}E_{n,S}^{(m)}-\dim_{\mathbb{F}}E_{n,S}^{(m+1)}$
are in terms of dimensions of spectral sequence. Finally, each nonzero
$\nu_{n,s,m}$ is determined recursively by terms from only the spectral
sequence. ∎

## References

  * [1] Basu, S., and Parida, L. Spectral sequences, exact couples and persistent homology of filtrations.  Expo. Math. 35, 1 (2017), 119–132.
  * [2] Edelsbrunner, H., and Harer, J. L. Computational topology.  American Mathematical Society, Providence, RI, 2010.  An introduction.
  * [3] Leray, J. Structure de l’anneau d’homologie d’une représentation.  C. R. Acad. Sci. Paris 222 (1946), 1419–1422.
  * [4] McCleary, J. A user’s guide to spectral sequences, second ed., vol. 58 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2001.
  * [5] Passman, D. S. A course in ring theory.  The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991.
  * [6] Rotman, J. J. An introduction to homological algebra, second ed.  Universitext. Springer, New York, 2009.
  * [7] Wu, H. A colored $sl(N)$ homology for links in $S^{3}$.  Dissertationes Math. 499 (2014), 217.
  * [8] Wu, H. Equivariant Khovanov-Rozansky homology and Lee-Gornik spectral sequence.  Quantum Topol. 6, 4 (2015), 515–607.
  * [9] Zomorodian, A., and Carlsson, G. Computing persistent homology.  Discrete Comput. Geom. 33, 2 (2005), 249–274.