Sunday, May 28, 2017

Čech (co)homology

In this post we briefly recall the construction of Čech cohomology as well as compute a few examples. Let $X$ be a topological space with a cover $\mathcal U = \{U_i\}$, $\mathcal F$ a $C$-valued sheaf on $X$, and $\widehat{\mathcal F}$ a $C$-valued cosheaf on $X$, for some category $C$ (usually abelian groups).

Definition: The nerve $N$ of $\mathcal U$ is the simplicial complex that has an $r$-simplex $\rho$ for every non-empty intersection of $r+1$ opens of $\mathcal U$. The support $U_\rho$ of $\rho$ is this non-empty intersection. The $r$-skeleton $N_r$ of $N$ is the collection of all $r$-simplices.

Remark: The sheaf $\mathcal F$ and cosheaf $\widehat {\mathcal F}$ may be viewed as being defined either on the opens of $\mathcal U$ over $X$, or on the nerve $N$ of $\mathcal U$. Indeed, the inclusion map $V\hookrightarrow U$ on opens is given by the forgetful map $\partial$. That is, $\partial_i:N_r\to N_{r-1}$ forgets the $i$th open defining $\rho\in N_r$, so if $U_\rho = U_0\cap \cdots \cap U_r$, then $U_{\partial_0\rho} = U_1\cap\cdots \cap U_r$.

The Čech (co)homology will be defined as the (co)homology of a particular complex, whose boundary maps will be induced by, equivalently, the inclusion map on opens or $\partial_i$ on simplices.

Definition: In the context above:
  • a $p$-chain is a finite formal sum of elements $a_{\sigma_i}\in \widehat{\mathcal F}(U_{\sigma_i})$, for every $\sigma_i$ a $p$-simplex,
  • a $q$-cochain is a finite formal sum of elements $b_{\tau_j}\in \mathcal F(U_{\tau_j})$, for every $\tau_j$ a $q$-simplex,
  • the $p$-differential is the map $d_p:\check C_p(\mathcal U,\mathcal F) \to \check C_{p-1}(\mathcal U,\mathcal F)$ given by
\[
d_p(a_\sigma) = \sum_{i=0}^p (-1)^i \widehat{\mathcal F}(\partial_i)(a_\sigma),\]
  • the $q$-codifferential is the map $\delta^q:\check C^q(\mathcal U,\mathcal F) \to \check C^{q+1}(\mathcal U,\mathcal F)$ given by
\[
\delta^q(b_\tau) = \sum_{j=0}^{q+1} (-1)^j \mathcal F(\partial_j)(b_\tau).\]The collection of $p$-chains form a group $\check C_p(\mathcal U,\mathcal F)$ and the collection of $q$-cochains also form a group $\check C^q(\mathcal U,\mathcal F)$, both under the respective group operation in each coordinate. The Čech homology $H_*(\mathcal U,\mathcal F)$ is the homology of the chain complex of $\check C_p$ groups, and the Čech cohomology $H^*(\mathcal U,\mathcal F)$ is the cohomology of the cochain complex of $\check C^q$ groups.

Example: Let $X=S^1$ with a cover $\mathcal U = \{U,V,W\}$ and associated nerve $N_{\mathcal U}$ as below.
The cover is chosen so that all intersections are contractible. Let $k$ be a field. Let $\widehat{\mathcal F}$ be a cosheaf over $N$ and $\mathcal F$ a sheaf over $N$, with $\widehat {\mathcal F}(\text{0-cell})=\mathcal F(\text{1-cell}) = (1,1)\in k^2$ and $\widehat{\mathcal F}(\text{1-cell})=\mathcal F(\text{0-cell})=1\in k$, so that the natural extension and restriction maps work. Then all the degree 0 and 1 chain and cochain groups are $k^3$. Giving a counter-clockwise orientation to $X$, we easily see that
\begin{align*}
d_1\sigma_{U\cap V} & = \sigma_V-\sigma_U, & \delta^0\sigma_U & = \sigma_{U\cap V}-\sigma_{W\cap U}, \\
d_1\sigma_{V\cap W} & = \sigma_W-\sigma_V, & \delta^0\sigma_V & = \sigma_{V\cap W}-\sigma_{U\cap V}, \\
d_1\sigma_{W\cap U} & = \sigma_U-\sigma_W, & \delta^0\sigma_W & = \sigma_{W\cap U}-\sigma_{V\cap W}.\end{align*}If we give an ordered basis of $(\sigma_{U\cap V},\sigma_{V\cap W},\sigma_{W\cap U})$ to $\check C_1(\mathcal U,\widehat{\mathcal F})$ and $\check C^1(\mathcal U,\mathcal F)$, and $(\sigma_U,\sigma_V,\sigma_W)$ to $\check C_0(\mathcal U,\widehat{\mathcal F})$ and $\check C^0(\mathcal U,\mathcal F)$, we find that
\[
d_1 = \begin{bmatrix}
-1 & 0 & 1 \\ 1 & -1 & 0 \\ 0 & 1 & -1
\end{bmatrix}
\sim
\begin{bmatrix}
1 & 0 & -1 \\ 0 & 1 & -1 \\ 0 & 0 & 0
\end{bmatrix},
\hspace{1cm}
\delta^0 = \begin{bmatrix}
-1 & 1 & 0 \\ 0 & -1 & 1 \\ 1 & 0 & -1
\end{bmatrix}
\sim
\begin{bmatrix}
1 & 0 & -1 \\ 0 & 1 & -1 \\ 0 & 0 & 0
\end{bmatrix}.
\]
The Čech chain and cochain complexes are then
\[
0 \to \check C_1(\mathcal U,\widehat{\mathcal F}) \tov{d_1} \check C_0(\mathcal U,\widehat{\mathcal F}) \to 0,
\hspace{1cm}
0 \to \check C^0(\mathcal U,\mathcal F) \tov{\delta^0} \check C^1(\mathcal U,\mathcal F) \to 0,\]for which
\begin{align*}
H_1(\mathcal U,\widehat{\mathcal F}) & = \ker(d_1) = k,
& H^0(\mathcal U,\mathcal F) & = \ker(\delta^0) = k, \\
H_0(\mathcal U,\widehat{\mathcal F}) & = k^3/\im(d_1) = k^3/k^2 = k,
& H^1(\mathcal U,\mathcal F) & = k^3/\im(\delta^0) = k^3/k^2 = k.\end{align*}By the Čech-de Rham theorem, we know that the (co)homology groups should agree with the usual groups for $S^1$, as $\mathcal U$ was a good cover, which they do. Next we compute another example with a view towards persistent homology.

Definition: Let $X$ be a topological space and $f:X\to Y$ a map with $\mathcal U$ covering $f(X)$. The Leray sheaf $L^i$ of degree $i$ over $N_{\mathcal U}$ is defined by $L^i(\sigma) = H^i(f^{-1}(U_\sigma))$ and $L^i(\sigma\hookrightarrow \tau) = H^i(f^{-1}(U_\tau)\hookrightarrow f^{-1}(U_\sigma))$, whenever $\sigma$ is a face of $\tau$.

Theorem (Curry, Theorem 8.2.21): In the context above, if $N_{\mathcal U}$ is at most 1-dimensional, then for any $t\in \R$,
\[
H^i(f^{-1}(-\infty,t])\cong H^0((-\infty,t],L^i)\oplus H^1((-\infty,t],L^{i-1}).\]
The idea is to apply this theorem in a filtration, for different values of $t$, but in the example below we will have $t$ large enough so that $X\subset f^{-1}(-\infty,t]$.

Example: Let $f:S^1\to \R$ be a projection map, and let $X = f(S^1)$ with a cover $\mathcal U = \{U,V\}$ as below.
Note that although $f^{-1}(U)\cap f^{-1}(V)$ is not contractible, $U\cap V$ is, and the Čech cohomology will be over $\mathcal U\subset \R$, so we are fine in applying the Čech-de Rham theorem. It is immediate that the only non-zero Leray sheaves are $L^0$, for which
\[
L^0(\sigma_U) = k,\hspace{1cm}
L^0(\sigma_V) = k,\hspace{1cm}
L^0(\sigma_{U\cap V}) = k^2,\]hence $\check C^0(\mathcal U,L^0)=\check C^1(\mathcal U,L^0) = k^2$. Giving $\check C^0(\mathcal U,L^0)$ the ordered basis $(\sigma_U,\sigma_V)$ and noting the homology maps $H^0(f^{-1}(U)\hookrightarrow f^{-1}(U\cap V))$ and $H^0(f^{-1}(V)\hookrightarrow f^{-1}(U\cap V))$ are simply $1\mapsto (1,1)$, the \v Cech complex is
\[
0 \to \check C^0(\mathcal U,L^0) \tov{\left[\begin{smallmatrix}-1 & -1 \\ 1 & 1 \end{smallmatrix}\right]} \check C^1(\mathcal U,L^0) \to 0.
\]
Hence $H^0(\mathcal U,L^0)=\ker(\delta^0)=k$ and $H^1(\mathcal U,L^0)=k^2/\im(\delta^0)=k^2/k=k$, allowing us to conclude, using Curry's and the Čech--de Rham theorems, that
\begin{align*}
H^0(S^1) & \cong H^0(\mathcal U,L^0) \oplus H^1(\mathcal U,L^{-1}) = k\oplus 0 = k, \\
H^1(S^1) & \cong H^0(\mathcal U,L^1) \oplus H^1(\mathcal U,L^0) = 0\oplus k = k, \\
H^2(S^1) & \cong H^0(\mathcal U,L^2) \oplus H^1(\mathcal U,L^1) = 0\oplus 0=0,\end{align*}as expected.

References: Bott and Tu (Differential forms in algebraic topology, Section 10), Bredon (Sheaf theory, Section VI.4), Curry (Sheaves, cosheaves, and applications, Section 8)

Sunday, May 21, 2017

Categories and the TDA pipeline

 Conference topic

This post contains topics and ideas from ACAT at HIM, April 2017, as presented by Professor Ulrich Bauer (see slide 11 of his presentation, online at ulrich-bauer.org/persistence-bonn-talk.pdf). The central theme is to assign categories and functors to analyze the process
\[
\text{filtration}\ \longrightarrow\ \text{(co)homology}\ \longrightarrow\ \text{barcode.}
\hspace{3cm}(\text{pipe}) \] Remark: The categories we will use are below. For filtrations, we have the ordered reals (though any poset $P$ would work) and topological spaces:
\begin{align*}
R\ :\ & \Obj(R) = \R,  & \Top\ :\ & \Obj(\Top) = \{\text{topological spaces}\}, \\[5pt]
& \Hom(r,s) = \begin{cases}
\{r \mapsto s\}, & \text{ if } r\leqslant s, \\ \emptyset, & \text{ else,}
\end{cases} && \Hom(X,Y) = \{\text{functions }f:X\to Y\}.
\end{align*}
For (co)homology groups, we have the category of (framed) vector spaces. We write $V^n$ for $V^{\oplus n} = V\oplus V\oplus \cdots \oplus V$, and $e_n$ for a frame of $V^n$ (see below).
\begin{align*}
\Vect\ :\ & \Obj(\Vect) = \{V^{\oplus n}\ :\ 0\leqslant n< \infty\},\\
& \Hom(V^n,V^m) = \{\text{homomorphisms }f:V^n\to V^m\}, \\[5pt]
\Vect^{fr}\ :\ & \Obj(\Vect^{fr}) = \{V^n\times e^n\ :\ 0\leqslant n<\infty\}, \\
& \Hom(V^n\times e^n,V^m\times e^m) = \{\text{hom. }f:V^n\to V^m,\ g:e^n\to e^m,\ g\in \Mat(n,m)\}.
\end{align*}
Finally for barcodes, we have $\Delta$, the category of finite ordered sets, and its variants. A partial injective function, or matching $f:A\nrightarrow B$ is a bijection $A'\to B'$ for some $A'\subseteq A$, $B'\subseteq B$.
\begin{align*}
\Delta\ :\ & \Obj(\Delta) = \{[n]=(0,1,\dots,n)\ :\ 0\leqslant n<\infty\},\\
& \Hom([n],[m]) = \{ \text{order-preserving functions }f:[n]\to [m]\}, \\[5pt]
\Delta'\ :\
& \Obj(\Delta')= \{a=(a_0<a_1<\cdots<a_n)\ :\ a_i\in \Z_{\geqslant 0}, 0\leqslant n<\infty\},\\ & \Hom(a,b) = \{\text{order-preserving functions }f:a\to b\}, \\[5pt]
\Delta''\ :\
& \Obj(\Delta'')= \{a=(a_0<a_1<\cdots<a_n)\ :\ a_i\in \Z_{\geqslant 0}, 0\leqslant n<\infty\},\\ & \Hom(a,b) = \{\text{order-preserving partial injective functions }f:a\nrightarrow b\}.
\end{align*}

Definition: A frame $e$ of a vector space $V^n$ is equivalently:
  • an ordered basis of $V^n$,
  • a linear isomorphism $V^n\to V^n$, or
  • an element in the fiber of the principal rank $n$ frame bundle over a point.
Frames (of possibly different sizes) are related by full rank elements of $\Mat(n,m)$, which contains all $n\times m$ matrices over a given field.

Definition: Let $(P,\leqslant)$ be a poset. A (indexed topological) filtration is a functor $F:P\to \Top$, with
\[
\Hom(F(r),F(s)) = \begin{cases}
\{\iota:F(r) \hookrightarrow F(s)\}, & \text{ if }r\leqslant s, \\ \emptyset, & \text{ else,}
\end{cases}
\]
where $\iota$ is the inclusion map. That is, we require $F(r)\subseteq F(s)$ whenever $r\leqslant s$.

Definition: A persistence module is the composition of functors $M_i:P \tov{F} \Top \tov{H_i} \Vect$.

Homology will be taken over some field $k$. A framed persistence module is the same composition as above, but mapping into $\Vect^{fr}$ instead. The framing is chosen to describe how many different vector spaces have already been encountered in the filtration.

Definition: A barcode is a collection of intervals of $\R$. It may also be viewed as the composition of functors $B_i:P\tov{F}\Top\tov{H_i}\Vect \tov{\dim}\Delta$.

Similarly as above, we may talk about a framed barcode by instead mapping into $\Vect^{fr}$ and then to $\Delta''$, keeping track of which vector spaces we have already encountered. This allows us to interpret the process $(\text{pipe})$ in two different ways. First we have the unframed approach
\[
\begin{array}{r c c c l}
\Top & \to & \Vect & \to & \Delta, \\
X_t & \mapsto & H_i(X_t;k) & \mapsto & [\dim(H_i(X_t;k))].
\end{array}
\]
The problem here is interpreting the inclusion $X_t\hookrightarrow X_{t'}$ as a map in $\Delta$, for instance, in the case when $H_i(X_t;k)\cong H_i(X_{t'};k)$, but $H_i(X_t\hookrightarrow X_{t'}) \neq \id$. To fix this, we have the framed interpretation of $(\text{pipe})$
\[
\begin{array}{r c c c l}
\Top & \to & \Vect^{fr} & \to & \Delta'', \\
X_t & \mapsto & H_i(X_t;k)\times e & \mapsto & [e].
\end{array}
\]
The first map produces a frame $e$ of size $n$, where $n$ is the total number of different vector spaces encountered over all $t'\leqslant t$, by setting the first $\dim(H_i(X_t;k))$ coordinates to be the appropriate ones, and then the rest. This is done with the second map to $\Delta''$ in mind, as the size of $[e]$ is $\dim(H_i(X_t;k))$, with only the first $\dim(H_i(X_t;k))$ basis vectors taken from $e$. As usual, these maps are best understood by example.

Example: Given the closed curve $X$ in $\R^2$ below, let $\varphi:X\to \R$ be the height map from the line 0, with $X_i=\varphi^{-1}(-\infty,i]$, for $i=r,s,t,u,v$. Let $e_i$ be the standard $i$th basis vector in $\R^N$.


Remark: This seems to make $(\text{pipe})$ functorial, as the maps $X_t\hookrightarrow X_{t'}$ may be naturally viewed as partial injective functions in $\Delta''$, to account for the problem mentioned with the unframed interpretation. However, we have traded locality for functoriality, as the image of $X_t$ in $\Delta''$ can not be calculated without having calculated $X_{t'}$ for all $t'<t$.

References: Bauer (Algebraic perspectives of persistence), Bauer and Lesnick (Induced matchings and the algebraic stability of persistence barcodes)