Saturday, June 24, 2017

A constructible sheaf over the Ran space

Let $M$ be a manifold. The goal of this post is to show that the sheaf $\mathcal F_{(P,t)}=\text{Rips}(P,t)$ valued in simplicial complexes over $\Ran^{\geqslant}(M)\times \R_{\geqslant 0}$ is constructible. This space will be described using filtered diagram of open sets, with the sheaf on consecutive differences of the diagram giving simplicial complexes of the same homotopy type.

Let $P=\{P_1,\dots,P_n\}\in \Ran(M)$. For every collection of open neighborhoods $\{U_i\owns P_i\}_{i=1}^n$ of the $P_i$ in $M$, there is an open neighborhood of $P$ in $\Ran(M)$ given by
\Ran(\{U_i\}_{i=1}^n) = \left\{Q\in \Ran(M)\ :\ Q\subset \bigcup_{i=1}^n U_i,\ Q\cap U_i\neq \emptyset\right\}.\]Moreover, these are a basis for any open neighborhood of $P$ in $\Ran(M)$.


We begin with a few facts about sets. Let $X$ be a topological space.

Lemma 1: Let $A,B\subset X$. Then:
  • (a) If $A\subset B$ is open and $B\subset X$ is open, then $A\subset X$ is open.
  • (b) If $A\subset B$ is closed and $B\subset X$ is open, then $A\subset X$ is locally closed.
  • (c) If $A\subset B$ is open and $B\subset X$ is locally closed, then $A\subset X$ is locally closed.
  • (d) If $A\subset B$ is locally closed and $B\subset X$ is locally closed, then $A\subset X$ is locally closed.
Proof: For part (a), first recall that open sets in $B$ are given by intersections of $B$ with open sets of $A$. Hence there is some $W\subset X$ open such that $A = B\cap W$. Since both $B$ and $W$ are open in $X$, the set $A$ is open in $X$.
     For part (b), since $A\subset B$ is closed, there is some $Z\subset X$ closed such that $A=B\cap Z$. Since $B$ is open in $X$, $A$ is locally closed in $X$.
     For parts (c) and (d), let $B = W_1\cap W_2$, for $W_1\subset X$ open and $W_2\subset X$ closed. For part (c), again there is some $W\subset X$ open such that $A = B\cap W$. Then $A = (W_1\cap W_2)\cap W = (W\cap W_1)\cap W_2$, and since $W\cap W_1$ is open in $X$, the set $A$ is locally closed in $X$.
     For part (d), let $A = Z_1\cap Z_2$, where $Z_1\subset B$ is open and $Z_2\subset B$ is closed. Then there exists $Y_1\subset X$ open such that $Z_1 = B\cap Y_1$ and $Y_2\subset X$ closed such that $Z_2 = B\cap Y_2$. So $A = Z_1\cap Z_2 = (B\cap Y_1) \cap (B\cap Y_2) = (B\cap Y_1)\cap Y_2$, where $(B\cap Y_1)\subset X$ is open and $Y_2\subset X$ is closed. Hence $A\subset X$ is locally closed. $\square$

Lemma 2: Let $U\subset X$ be open and $f:X\to \R$ continuous. Then $\bigcup_{x\in U}\{x\}\times (f(x),\infty)$ is open in $X\times \R$.

Proof: Consider the function
\begin{array}{r c l}
g\ :\ X\times \R & \to & X\times \R, \\
(x,t) & \mapsto & (x,t-f(x)).
\end{array}\]Since $f$ is continuous and subtraction is continuous, $g$ is continuous (in the product topology). Since $U\times (0,\infty)$ is open in $X\times \R$, the set $g^{-1}(U\times (0,\infty))$ is open in $X\times \R$. This is exactly the desired set. $\square$

Filtered diagrams

Definition: A filtered diagram is a directed graph such that
  • for every pair of nodes $u,v$ there is a node $w$ such that there exist paths $u\to w$ and $v\to w$, and
  • for every multi-edge $u\stackrel{1,2}\to v$, there is a node $w$ such that $u\stackrel 1\to v\to w$ is the same as $u\stackrel2\to v\to w$.
For our purposes, the nodes of a filtered diagram will be subsets of $\Ran^n(M)\times \R_{\geqslant 0}$ and a directed edge will be open inclusion of one set into another set (that is, the first is open inside the second). Although we require below that loops $u\to u$ be removed, we consider the first condition above to be satisfied if there exists a path $u\to v$ or a path $v\to u$.

Remark: In the context given,
  • edge loops $U\to U$ and path loops $U\to\cdots\to U$ may be replaced by a single node $U$ ($U\subseteq U$ is the identity),
  • multi-edges $U\stackrel{1,2}\to V$ may be replaced by a single edge $U\to V$ (inclusions are unique), and
  • multi-edges $U\to V\to U$ may be replaced by a single node $U$ (if $U\subseteq V$ and $V\subseteq U$, then $U=V$).
A diagram with all possible replacements of the types above is called a reduced diagram.
Lemma 3: In the context above, a reduced filtered diagram $D$ of open sets of any topological space $X$ gives an increasing sequence of open subsets of $X$, with the same number of nodes.

Proof: Order the nodes of $D$ so that if $U\to V$ is a path, then $U$ has a lower index than $V$ (this is always possible in a reduced diagram). Let $U_1,U_2,\dots,U_N$ be the order of nodes of $D$ (we assume we have finitely many nodes). For every pair of indices $i,j$, set
\delta_{ij} = \begin{cases}
\emptyset & \text{ if }U_i\to U_j\text{ is a path in }D, \\
U_i & \text{ if }U_i\to U_j\text{ is not a path in }D.
\end{cases}\]Then the following sequence is an increasing sequence of nested open subsets of $X$:
U_1 \to \delta_{12} \cup U_2 \to \delta_{13}\cup \delta_{23}\cup U_3 \to \cdots \to \underbrace{\left(\bigcup_{i=1}^{j-1}\delta_{ij} \right)\cup U_j}_{V_j} \to \cdots \to U_N.\]Indeed, if $U_i \to U_j$ is a path in $D$, then $U_i$ is open in $V_j$, as $U_i\subset V_j$. If $U_i\to U_j$ is not a path in $D$, then $U_i$ is still open in $V_j$, as $U_i\subset V_j$. As unions of opens are open, and by Lemma 1(a), $V_{j-1}$ is open in $V_j$ for all $1<j<N$. $\square$

Remark 4: Note that every consecutive difference $V_j\setminus V_{j-1}$ is a (not necessarily proper) subset of $U_j$.

Definition 5: For $k\in \Z_{>0}$, define a filtered diagram $D_k$ over $\Ran^k(M)\times \R_{\geqslant 0}$ by assigning a subset to every corner of the unit $N$-hypercube in the following way: for the ordered set $S=\{(i,j) \ :\ 1\geqslant i<j\geqslant k\}$ (with $|S|=N=k(k-1)/2$), write $P=\{P_1,\dots,P_k\}\in \Ran^k(M)$, and assign
(\delta_1,\dots,\delta_k) \mapsto \left\{
(P,t)\in \Ran^k(M)\times \R_{\geqslant 0}\ :\ t>d(P_{(S_\ell)_1},P_{(S_\ell)_2}) \text{ whenever }\delta_\ell=0,\ \forall\ 1\leqslant \ell\leqslant k
\right\},\]where $\delta_\ell\in \{0,1\}$ for all $\ell$, and $d(x,y)$ is the distance on the manifold $M$ between $x,y\in M$. The edges are directed from smaller to larger sets.

Remark 6: This diagram has $2^{k(k-1)/2}$ nodes, as $k(k-1)/2$ is the number of pairwise distances to consider. Moreover, the difference between the head and tail of every directed edge is elements $(P,t)$ for which $\text{Rips}(P,t)$ is constant. 

Example: For example, if $k=3$, then $2^{3\cdot2/2}=8$, and $D_3$ is the diagram below. For ease of notation, we write $\{t>\cdots\}$ to mean $\{(P,t)\ :\ P=\{P_1,P_2,P_3\}\in \Ran^3(M),\ t>\cdots\}$.

The diagram of corresponding Vietoris-Rips complexes introduced at each node is below. Note that each node contains elements $(P,t)$ whose Vietoris-Rips complex may be of type encountered in any paths leading to the node.

Lemma 7: In the filtered diagram $D_k$, every node is open inside every node following it.

Proof: The left-most node of $D_k$ may be expressed as
\{(P,t)\ :\ P=\{P_1,\dots,P_k\}\in \Ran^k(M), t>d(P_i,P_j)\ \forall\ P_i,P_j\in P\} = \bigcup_{P\in \Ran^k(M)} \{P\}\times \left(\max_{P_i,P_j\in P}\{d(P_i,P_j)\},\infty\right).\] Applying a slight variant of Lemma 2 (replacing $\R$ by an open ray that is bounded below), with the $\max$ function continuous, we get that the left-most node is open in the nodes one directed edge away from it. Repeating this argument, we get that every node is open inside every node following it. $\square$

The constructible sheaf

Recall that a constructible sheaf can be given in terms of a nested cover of opens or a cover of locally closed sets (see post "Constructible sheaves," 2017-06-13). The approach we take is more the latter, and illustrates the relation between the two. Let $n\in \Z_{>0}$ be fixed.

Definition: Define a sheaf $\mathcal F$ over $X=\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$ valued in simplicial complexes, where the stalk $\mathcal F_{(P,t)}$ is the Vietoris--Rips complex of radius $t$ on the set $P$. For any subset $U\subset X$ such that $\mathcal F_{(P,t)}$ is constant for all $(p,t)\in U$, let $\mathcal F(U)=\mathcal F_{(P,t)}$.

Theorem: The sheaf $\mathcal F$ is constructible.

Proof: First, by Remark in Lurie, we have that $\Ran^{n}(M)$ is open in $\Ran^{\leqslant n}(M)$. Hence $\Ran^{\leqslant n-1}(M)$ is closed in $\Ran^{\leqslant n}(M)$. Similarly, $\Ran^{\leqslant n-2}(M)$ is closed in $\Ran^{\leqslant n-1}(M)$, and so closed in $\Ran^{\leqslant n}(M)$, meaning that $\Ran^{\leqslant k}(M)$ is closed in $\Ran^{\leqslant n}(M)$ for all $1\leqslant k\leqslant n$. This implies that $\Ran^{\geqslant k}(M)$ is open in $\Ran^{\leqslant n}(M)$ for all $1\leqslant k\leqslant n$, meaning that $\Ran^k(M)$ is locally closed in $\Ran^{\leqslant n}(M)$, for all $1\leqslant k\leqslant n$.
     Next, for every $1\leqslant k\leqslant n$, let $V_{k,1}\to \cdots \to V_{k,N_k}$ be a sequence of nested opens covering $\Ran^k(M)\times \R_{\geqslant 0}$, as given in Definition 5 and flattened by Lemma 3. The sets are open by Lemma 7. This gives a cover $\mathcal V_k = \{V_{k,1},V_{k,2},\setminus V_{k,1},\dots,V_{k,N_k}\setminus V_{k,N_k-1}\}$ of $\Ran^k(M)\times \R_{\geqslant 0}=V_{k,N_k}$ by consecutive differences, with $V_{k,1}$ open in $V_{k,N_k}$ and all other elements of $\mathcal V_k$ locally closed in $V_{k,N_k}$, by Lemma 1(b). By Lemma 1 parts (c) and (d), every element of $\mathcal V_k$ is locally closed in $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$, and so $\mathcal V = \bigcup_{k=1}^n \mathcal V_k$ covers $\Ran^{\leqslant n}(M)\times \R_{\geqslant 0}$ by locally closed subsets.
     Finally, by Remarks 4 and 6, over every $V\in\mathcal V$ the function $\text{Rips}(P,t)$ is constant. Hence $\mathcal F|_V$ is a locally constant sheaf, for every $V\in \mathcal V$. As the $V$ are locally closed and cover $X$, $\mathcal F$ is constructible. $\square$

References: Lurie (Higher algebra, Section 5.5.1)

Tuesday, June 13, 2017

Constructible sheaves

Let $X$ be a topological space with an open cover $\mathcal U = \{U_i\}$, and category $Op(X)$ of open sets of $X$. The goal is to define constructible sheaves and consider some applications. Thanks to Joe Berner for helpful pointers in this area.

Definition: Constructible subsets of $X$ are the smallest family $F$ of subsets of $X$ such that
  • $Op(X)\subset F$,
  • $F$ is closed under finite intersections, and
  • $F$ is closed under complements.
This idea can be applied to sheaves. Recall that a locally closed subset of $X$ is the intersection of an open set and a closed set.

Definition: A sheaf $\mathcal F$ over $X$ is constructible if there exists, equivalently,
  • a filtration $\emptyset=U_0\subset \cdots \subset U_n=X$ of $X$ by opens such that $\mathcal F|_{U_{i+1}\setminus U_i}$ is constant for all $i$, or
  • a cover $\{V_i\}$ of locally closed subsets of $X$ such that $\mathcal F|_{V_i}$ is constant for all $i$.
Since the category of abelian sheaves over a topological space has enough injectives, we may consider an injective resolution of a sheaf $\mathcal F$ rather than the sheaf itself. The resolution may be considered as living inside the derived category of sheaves on $X$.

Definition: Let $A$ be an abelian category.
  • $C(A)$ is the category of cochain complexes of $A$, 
  • $K(A) = C(A)$ modulo cochain homotopy, and
  • $D(A) = K(A)$ modulo $F\in K(A)$ such that $H^n(F)=0$ for all $n$, called the derived category of $A$.
Next we consider an example. Recall the Ran space $\Ran(M) = \{X\subset M\ :\ 0<|X|<\infty\}$ of non-empty finite subsets of a manifold $M$ and the Čech complex of radius $t>0$ of $P\in \Ran(M)$, a simplicial complex with $n$-cells for every $P'\subset P$ of size $n+1$ such that $d(P'_1,P'_2)<t$ for all $P'_1,P'_2\in P'$.

Example: Consider the subset $\Ran^{\leqslant 2}(M) = \{X\subset M\ :\ 1\leqslant |X|\leqslant 2\}$ of the Ran space. Decompose $X=\Ran^{\leqslant 2}(M)\times \R_+$ into disjoint sets $U_\alpha\cup U_\beta$, where
U_\alpha = \underbrace{\left(\Ran^1(M)\times \R_+\right)}_{U_{\alpha,1}} \cup \underbrace{\bigcup_{P\in \Ran^2(M)}\{P\}\times (d_M(P_1,P_2),\infty)}_{U_{\alpha,2}},
U_\beta = \bigcup_{P\in \Ran^2(M)} \{P\} \times (0,d_M(P_1,P_2)],
with $d_M$ the distance on the manifold $M$. The idea is that for every $(P,t)\in U_\alpha$, the Čech complex of radius $t$ on $P$ has the homotopy type of a point, whereas on $U_\beta$ has the homotopy type of two points. With this in mind, define a constructible sheaf $F\in\text{Shv}(\Ran^{\leqslant 2}(M)\times \R_+)$ valued in simplicial complexes, with $F|_{U_\alpha}$ and $F|_{U_\beta}$ constant sheaves. Set
F_{(P,t)\in U_\alpha} = F(U_\alpha) = \left(0\to \{*\} \to 0\right),
F_{(P,t)\in U_\beta} = F(U_\beta) = \left(0\to \{*,*\}\to 0\right).
Note that the chain complex $F(U_\alpha)$ is chain homotopic to $0\to \{-\}\to \{*,*\}\to 0$, where $-$ is a single 1-cell with endpoints $*,*$. To show that this is a constructible sheaf, we need to filter $\Ran^{\leqslant 2}(M)\times \R_+$ into an increasing sequence of opens. For this we use a distance on $\Ran^{\leqslant 2}(M)\times \R_+$, given by $d((P,t),(P',t'))=d_{\Ran(M)}(P,P')+d_\R(t,t'),$ where $d_\R(t,t')=|t-t'|$ and
d_{\Ran(M)}(P,P')=\max_{p\in P}\left\{\min_{p'\in P'}\left\{d_M(p,p')\right\}\right\} + \max_{p'\in P'}\left\{\min_{p\in P}\left\{d_M(p,p')\right\}\right\}.
Note that $U_\alpha$ is open. Indeed, for $(P,t)\in U_{\alpha,1}$, every other $P'\in \Ran^1(M)$ close to $P$ is also in $U_{\alpha,1}$, and if $P'\in \Ran^2(M)$ is close to $P$, then the non-zero component $t\in\R_+$ still guarantees the same homotopy type. The set $U_{\alpha,2}$ is open as well, so $U_\alpha$ is open. The whole space is open, so a filtration $\emptyset\subset U_\alpha\subset X$ works for us.

References: Hartshorne (Algebraic geometry, Section II.3), Hartshorne (Residues and Duality, Chapter IV.1), Kashiwara and Schapira (Sheaves on manifolds, Chapters 2 and 8), Lurie (Higher algebra, Section 5.5.1)

Sunday, June 4, 2017

Sheaves and cosheaves

Let $X$ be a topological space with an open cover $\mathcal U = \{U_i\}$, and category $Op(X)$ of open sets of $X$. Let $C$ be any abelian category, most often groups.

Definition: A presheaf $\mathcal F$ over $X$ is a functor $Op(X)^{op}\to D$, and a sheaf if it satisfies the gluing axiom. A precosheaf $\widehat{\mathcal F}$ over $X$ is a functor $Op(X)\to D$, and a cosheaf if it satisfies the cutting axiom.

The gluing axiom may be interpreted as a colimit condition and the cutting axiom (thanks to Keaton Quinn for suggesting the name) may be interpreted as a limit condition. The components of sheaves and cosheaves are compared in the table below.
& \text{sheaf} & \text{cosheaf} \\\hline
\text{functoriality} & \begin{array}{r c l}
Op(S)^{op} & \to & D \\
U & \mapsto & \mathcal F(U)\\
(V\hookrightarrow U)^{op} & \mapsto & (\rho_{UV}:\mathcal F(U)\to \mathcal F(V))
\begin{array}{r c l}
Op(S) & \to & D \\
U & \mapsto & \widehat{\mathcal F}(U)\\
(V\hookrightarrow U) & \mapsto & (\varepsilon_{VU}:\widehat{\mathcal F}(V)\to \widehat{\mathcal F}(U))
\text{gluing / cutting} &
\begin{array}{r l}
\text{if} &  s_i|_{U_i\cap U_j}=s_j|_{U_i\cap U_j},\\[5pt]
\text{then} & \begin{array}{c}\exists s\in \mathcal F(U_i\cup U_j) \text{ s.t.}\\ s|_{U_i}=s_i,s|_{U_j}=s_j. \end{array}
\begin{array}{r l}
\text{if} & s_i|^{U_i\cup U_j}=s_j|^{U_i\cup U_j},\\[5pt]
\text{then} & \begin{array}{c}\exists s\in \widehat{\mathcal F}(U_i\cap U_j) \text{ s.t.}\\ s|^{U_i}=s_i,s|^{U_j}=s_j. \end{array}
\text{colimit / limit cond.} &
\mathcal F(U)\tov\cong \displaystyle\varprojlim_{V\subseteq U} \mathcal F(V)
\widehat{\mathcal F}(U)\xleftarrow{\hspace{3pt}\cong\hspace{3pt}} \displaystyle\varinjlim_{V\subseteq U} \widehat{\mathcal F}(V)
The maps $\rho_{UV}$ are called restrictions and $\varepsilon_{VU}$ are called extensions. Above, $s_i$ is a (co)section over $U_i$ and $s_j$ is a (co)section over $U_j$. For $s$ a (co)section of $U$ with $V\subset U\subset W$, write $s|_V$ for $\rho_{UV}(s)$ and $s|^W$ for $\varepsilon_{UW}(s)$. The isomorphisms with the colimits and limits are the natural maps from the respective colimit and limit diagrams.

Now we relate sheaves to persistent homology. All cohomology is be taken over a field $k$.

Remark: Suppose we have a finite point sample $P$ and some $t>0$, for which we can construct the nerve $N_{t,P}$, a cellular complex, of the union of balls of radius $t$ around the points of $P$. If $t'<t$, then there is a natural inclusion $N_{t',P}\hookrightarrow N_{t,P}$, which induces a map $H_\ell(N_{t',P})\to H_\ell(N_{t,P})$ on degree $\ell$ homology groups. Define a sheaf $\mathcal F^\ell$ over $\R$ for which
\mathcal F^\ell(U) = H^\ell(N_{\inf(U),P}),
\mathcal F^\ell_t = H^\ell(N_{t,P}).
This is indeed a sheaf, as $V\subseteq U$ implies that $\inf(U)\leqslant \inf(V)$, giving a natural map $\mathcal F^\ell(U)\to \mathcal F^\ell(V)$. The gluing axiom is also satisfied: assume without loss of generality that $\inf(U_i)\leqslant \inf(U_j)$ and take $s_i\in \mathcal F^\ell(U_i)$, $s_j\in \mathcal F^\ell(U_j)$ with the assumptions as above. Then $\inf(U_i)=\inf(U_i\cup U_j)$ and $\inf(U_j) = \inf(U_i\cap U_j)$, so
\mathcal F^\ell(U_i) = \mathcal F^\ell(U_i\cup U_j),
\mathcal F^\ell(U_j) = \mathcal F^\ell(U_i\cap U_j),
hence $s_i=s\in \mathcal F^\ell(U_i\cup U_j)$ and $s|_{U_j} = s_i|_{U_j} = s_i|_{U_i\cap U_j} = s_j|_{U_i\cap U_j} = s_j|_{U_j} = s_j$. Therefore sheaves capture all the persistent homology data. Note we do not take the sheaf cohomology of $\mathcal F^\ell$, instead the usual sequence of homology groups is induced by any increasing sequence in $\R$.

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

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
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
1 & 0 & -1 \\ 0 & 1 & -1 \\ 0 & 0 & 0
\delta^0 = \begin{bmatrix}
-1 & 1 & 0 \\ 0 & -1 & 1 \\ 1 & 0 & -1
1 & 0 & -1 \\ 0 & 1 & -1 \\ 0 & 0 & 0
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,
0 \to \check C^0(\mathcal U,\mathcal F) \tov{\delta^0} \check C^1(\mathcal U,\mathcal F) \to 0,\]for which
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
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 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:
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\}.
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).
\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)\}.
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$.
\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\}.

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,}
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))].
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].
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)

Sunday, April 9, 2017

Distance and persistence diagrams

We assume we have a Morse-type function $f:X\to \R$, whose associated persistence diagram is $D(f) = \{f_1,\dots,f_n\}$, which we will think of as a collection of persistence birth-death pairs $f_i$ in the extended real plane $(\R^*)^2$. If the topological space $X$ was filtered without such a function, define one by $x\mapsto i$ where $i$ is the smallest index such that $x\in X_i$.

Definition: Let $f,g:X\to \R$ be two Morse-type functions with associated persistence diagrams $D(f)$, $D(g)$. The (Wasserstein) $q$-distance between $f$ and $g$ is defined as
W_q(f,g) := \inf_{\sigma\in S_n} \left(\sum_{i=1}^n ||f_i-g_{\sigma(i)}||^q_\infty\right)^{1/q}.\]The bottleneck distance between $f$ and $g$ is
W_\infty(f,g) & := \lim_{q\to\infty} \left\{W_q(f,g)\right\} & (\text{limit of $q$-distances}) \\
& = \max_i\left\{||f_i-g_{\sigma(i)}||_\infty\ :\ \sigma = \arg W_q(f,g)\right\}. & (\text{length of longest edge in best matching})
Example: Consider the torus of inner and outer radius 1 embedded in the natural way. Left $f,g:T^2\to \R$ be height functions of the torus, but projecting to the planes $z=-2$ and $z=x-4$, respectively. Note all critical points occur on the plane $y=0$. Below, the slice at this plane is given (distances along planes from the first critical point are shown), as well as $D(f), D(g)$ on the same diagram (degrees of homology classes are shown).
For $D(f) = \{(0,\infty),(2,\infty),(4,\infty),(6,\infty)\}$ and $D(g) = \{(0,\infty), (2,\infty),(2\sqrt 2,\infty),(2+2\sqrt 2,\infty)\}$, it is clear that $\sigma=\id$ will be the best matching. The $q$-distance between $f$ and $g$ is then given by
W_q(f,g) = \left(||(4,\infty)-(2\sqrt 2,\infty)||^q_\infty+||(6,\infty)-(2+2\sqrt 2,\infty)||^q_\infty\right)^{1/q} = 2^{1/q}(4-2\sqrt 2),\]with bottleneck distance $4-2\sqrt2$. However, we would like to say that these two functions are the same in some way, as no critical points are switched, and extended persistence allows us to do that. The decomposed extended persistence module is given below.
The extended persistence classes have length 3 ($(1,4)$ for the 0-class, $(4,1)$ for the 2-class) and 1 ($(2,3)$ and $(3,2)$ for the 1-classes), no matter if we use $f$ or $g$ to define the $X_i$ and $X^j$.

Remark: An interesting question to ask is how long does it take for an essential homology class to be built? Some things to keep in mind while resolving this question:
  • The 0-class case should be treated spearately because of reduced homology
  • A class may be encountered several times (like the first 1-class in the example above)
  • What does it mean for a class to be "begin being built" (this is probably the key)
  • A class is certainly "done being built" (the first time) when it first appears in the persistence module
It seems that the extended persistence pair gives the length between when the class is "done being built" the first time $f$ encounters it fully and when it "begins to be built" the last time $f$ encounters it.

The bottleneck distance satisfies a nice stability condition for tame functions $f:X\to \R$, which have finite dimensional homology groups $H_k(f^{-1}(-\infty,a])$ for all $a\in \R$.

Theorem (Cohen-Steiner, Edelsbrunner, Harer 2007): Let $f,g:X\to \R$ be tame. Then $W_\infty(f,g) \leqslant ||f-g||_\infty$.

This bound is reached when $g=f+c$ for some constant $c$, and the Wasserstein distance is 0 when $g(p_i)=f(p_i)$ for all critical values. Hence it seems without stronger assumptions about $f$ and $g$, this bound is as good as we can get.

References: Edelsbrunner and Morozov (Persistent homology: theory and practice), Cohen-Steiner, Edelsbrunner and Harer (Stability of persistence diagrams)

Monday, March 27, 2017

Revisiting persistent homology

Here we revisit and expand on persistent homology, previously in the post "Persistent homology (an example)," 2016-05-19. All homology, except where noted, will be over a field $k$, and $X$ will be a topological space. Often a Morse-type function $f:X\to \R$ is introduced along with $X$, but we will try to take a more abstract view.

Definition: The space $X$ may be described as a filtered space with a filtration of sublevel sets
\[ \emptyset = X_0 \subseteq X_1\subseteq \cdots \subseteq X_m = X, \] whose persistence module is the (not necessarily exact) sequence
\[ 0 = H(X_0) \to H(X_1)\to\cdots \to H(X_m) = H(X) \] of homology groups of the filtration.

Remark: Every persistence module may be uniquely decomposed as a direct sum of sequences $0\to k\to \cdots\to k\to 0$, where every map is $\id$, except the first and last. The indices at which each sequence in the summand has its first and last non-zero map are called the birth and death of the homology class represented by the sequence.

In some cases a homology class may not die, so we consider the extended persistence module to make everything finite. We introduce the superlevel sets $X^i = X\setminus X_i$. If $f$ was our Morse-type function for $X$, with critical points $p_1<\cdots<p_m$, then for $t_0<p_1<t_1<\cdots<p_m<t_m$, we set $X_i = f^{-1}(-\infty,t_i]$ and $X^i = f^{-1}[t_i,\infty)$. The extended persistence module of $X$ is
0 = H_k(X_0) \to H_k(X_1)\to\cdots \to H_k(X_m) \to H_k(X,X^m) \to H_k(X,X^{m-1}) \to \cdots \to H_k(X,X^0)=0.
Definition: The persistence of a homology class in a persistence module conveys the idea of how long it is alive, presented by a persistence pair.
The persistence of all homology classes in a persistence module is often presented in a persistence diagram, the collection of persistence pairs $(i,j)$, or $(p_i,p_j)$ or $(f(p_i),f(p_j))$, as desired; or a linear barcode, the collection of persistence pairs $(i,j)$ as intervals $[i,j]$, ordered vertically. 

Example: Let $X = T^n=(S^1)^n$ be the $n$-torus. One filtration of $X$ is $X_0=\emptyset$ and $X_i = T^i$ for $1\leqslant i\leqslant n$. Note that $H_k(T^n,T^n\setminus X_n)=H_k(T^n)$ and $H_k(T^n,T^n\setminus X_0)=H_k(\emptyset)$. The first $n+1$ modules of the extended persistence module at level $k$ split into $\binom nk$ sequences, as $H_k(T^n) = \Z^{\binom nk}$. Geometric considerations allow $X^i = T^n\setminus T^i$ to be simplified in some cases. For instance, when $n=3$ and $k=0,1$ we have that $\widetilde H_k(T^3,T^3\setminus T^2)\cong \widetilde H_k(T^3,T^2) \cong \widetilde H_k(T^3/T^2)$, and knowing that $X^1=T^3\setminus T^1\simeq (S^1\vee S^1)\times S^1$, the relevant part of the long exact sequence for relative homology is

The two 1-cycles from $S^1\vee S^1\subset X^1$ map via $f$ to the same 1-cycle in $T^3$, hence $\text{im}(g)=\Z^2$. By exactness, $\text{ker}(g)=\Z^2$, and as $g$ is surjective, $A=\Z$.  Hence the extended persistence $k$-modules decompose as 
The persistence pairs are $(1,3)$ with multiplicity 2 and $(2,3)$, $(3,1)$ with multiplicity 1. The persistence diagrams and barcodes of the degree 0 and 1 homology classes are given below.
The diagonal $y=x$ is often given to indicate how short a lifespan a class has. Barcodes are usually not given for extended persistence diagrams, as length of a class (birth to death) is less important than position (above or below the diagonal).

Now we consider some generalizations of the ideas presented above.

Remark: A filtration can also be viewed as a diagram $X_0 \to X_1 \to \cdots \to X_m$, where each arrow is the inclusion map. We could generalize and consider a zigzag diagram, a sequence $X_0 \leftrightarrow X_1 \leftrightarrow \cdots \leftrightarrow X_m$, where $\leftrightarrow$ represents either $\to$ or $\leftarrow$. Homology can be applied and the resulting seuquence can also be uniquely decomposed into summands $k \leftrightarrow \cdots \leftrightarrow k$ where every arrow is the identity, giving zigzag persistent homology.

Remark: A filtration could also be viewed as a functor $F:\{0,\dots,m\}\to \text{Top}$, where $F(i)=X_i$ and $F(i\to j)$, for $j\>i$, is the composition of maps $X_i\to \cdots \to X_j$. Hence the degree-$k$ persistent homology of $X_i$ can be defined as the image of the maps $H_kF(i\to j)$, for all $j\>i$, and the functor $H_kF:\{0,\dots,m\}\to \text{Vec}$ may be viewed as the $k$th persistence module. This is a categorification of persistent homology.

Remark: A space $X$ can be filtered in several different ways. A multifiltration $X_\alpha$, for $\alpha$ a multi-index, is a collection of filtrations such that fixing all but one of the indices in $\alpha$ gives a (one-dimensional) filtration of $X$. The multidimensional persistence of $X_\alpha$ is a $|\alpha|$-dimensional grid of homology groups, with the barcode generalizing to the rank invariant, a map on the grid.

Another generalization, viewing filtrations as quivers, will not be discussed here, but rather presented as a separate post later.

References: Edelsbrunner and Morozov (Persistent homology: theory and practice), Carlsson, de Silva, and Morozov (Zigzag persistent homology and real-valued functions), Bubenik and Scott (Categorification of persistent homology), Carlsson and Zomorodian (The theory of multidimensional persistence)