Friday, August 11, 2017

The Ran space and singularity sets

Fix a manifold $M$ along with an embedding of $M$ into $\R^N$ and set $X=\Ran(M)\times \R_{\geqslant 0}$. The goal of this post is to show that every $(P,t)\in X$ has an open neighborhood that contains no points of the type $(Q,d(Q_i,Q_j))$, for some $i\neq j$. The collection of all such elements of $X$ is called the singularity set of $X$, as the Vietoris-Rips complex at $Q$ with such a radius changes at such elements.

Following Lurie, given a collection of open sets $\{U_i\}_{i=1}^k$ in $M$, set
\[\Ran(\{U_i\}_{i=1}^k) = \left\{P\in \Ran(M)\ :\ P\subset \bigcup_{i=1}^k U_i,\ P\cap U_i\neq \emptyset\ \forall\ i\right\}.\]
The topology on $\Ran(M)$ is the smallest topology for which every $\Ran(\{U_i\}_{i=1}^k)$ is open, for any $\{U_i\}_{i=1}^k$, for any $k$. The topology on the product $X$ is the product topology.

Remark: Note that the Ran space $\Ran(M)$ by itself can be split up into the pieces $\Ran^k(M)$, with "singularities" viewed as when a point splits into two (or more) points, or two (or more) combine into one. Then every element of $\Ran(M)$ is on the edge of the singularity set, as any neighborhood of a single point on the manifold contains two points on the manifold.

Fix $(P,t)\in X$ not in the singularity set of $X$, with $P=(P_1,\dots,P_k)$, for $1\leqslant k\leqslant n$. Set
\[\mu = \min\left\{t,\min_{1\leqslant i<j\leqslant k}\left\{|t-d(P_i,P_j)|\right\}\right\},\]
with distance $d$ being Euclidean distance in $\R^N$. The quantity $\mu$ should be thought of as the upper bound on how "far" we may move from $(P,t)$ without hitting the singularity set.

Proposition: Let $(P,t)$ be as above and $t,\alpha,\beta>0$ such that $\alpha+\beta=\mu$. Then
\[U=\Ran\left(\{B(P_i,\alpha/2)\}_{i=1}^k\right) \times \left(t-\beta,t+\beta\right)\]
is an open neighborhood of $(P,t)$ in $X$ and does not contain any points of the singularity set of $X$.

If $t=0$, then having $[0,\beta)$ as the second component of $U$, with $\alpha+\beta=\min_{i,j}d(P_i,P_j)$ works as the open neighborhood of $(P,t)$. The balls $B(x,r)$ are $N$-dimensional in $\R^N$. The proof is mostly applications of the triangle inequality.

Proof: By construction we have that $U$ is open in $X$ and that it contains $(P,t)$. For $(Q,s)\in U$ any other element, we have three cases. We will show that the distance between any two $Q_a,Q_b\in Q$ is never $s$. Fix distinct indices $\ell,m\in \{1,\dots,k\}$.
  1.  Case 1: $Q_a,Q_b\in B(P_\ell,\alpha/2)$. The situation looks as in the diagram below.
    Observe that $d(Q_a,Q_b)\leqslant d((Q_a,P_\ell)+d(Q_b,P_\ell) <\alpha = \mu-\beta \leqslant t-\beta$. Hence $d(Q_a,Q_b)<s$.
  2. Case 2: $Q_a\in B(P_\ell,\alpha/2), Q_b\in B(P_m,\alpha/2), d(P_\ell,P_m)>t$. The situation looks as in the diagram below.
    Observe that $d(P_\ell,P_m)\leqslant d(P_\ell,Q_b)+d(P_m,Q_b)\leqslant d(P_\ell,Q_a)+d(Q_a,Q_b)+d(P_m,Q_b) < \alpha+d(Q_a,Q_b)$. Since $d(P_\ell,P_m)>t$, the definition of $\mu$ gives us that $\mu \leqslant d(P_\ell,P_m)-t$, so combining this with the previous inequality, we get $d(Q_a,Q_b) > d(P_\ell,P_m)-\alpha\geqslant \mu+t-(\mu-\beta)=t+\beta$. Hence $d(Q_a,Q_b)>s$.
  3. Case 3: $Q_a\in B(P_\ell,\alpha/2), Q_b\in B(P_m,\alpha/2), d(P_\ell,P_m)<t$. The situation looks as in the diagram below.
    Observe that $d(Q_a,Q_b)\leqslant d(P_m,Q_b) + d(P_m,Q_a) \leqslant d(P_\ell,Q_a)+d(P_\ell,P_m)+d(P_m,Q_a)<\alpha+d(P_\ell,P_m)$. Since $d(P_\ell,P_m)<t$, the definition of $\mu$ gives us that $\mu\leqslant t-d(P_\ell,P_m)$, so combining this with the previous inequality, we get $d(Q_a,Q_b)<\mu-\beta+t-\mu = t-\beta$. Hence $d(Q_a,Q_b)<s$. $\square$
As an extension, it would be nice to show that the Vietoris--Rips complex of every element in $U$ is homotopy equivalent. This seems to be intuitively true, but a similar case analysis as above seems daunting.

References: Lurie (Higher Algebra, Section 5.5.1)

Thursday, August 3, 2017

New directions in TDA

 Conference topic

This post is informal, meant as a collection of (personally) new things from the workshop "Topological data analysis: Developing abstract foundations" at the Banff International Research Station, July 31 - August 4, 2017. New actual questions:
  1. Does there exist a constructible sheaf valued in persistence modules over $\Ran^{\leqslant n}(M)$?
    • On the stalks it should be the persistence module of $P\in \Ran^{\leqslant n}(M)$. What about arbitrary open sets?
    • Is there such a thing as a colimit of persistence modules?
    • Uli Bauer suggested something to do with ordering the elements of the sample and taking small open sets.
  2. Can framed vector spaces be used to make the TDA pipeline functorial? Does Ezra Miller's work help?
    • Should be a functor from $(\R,\leqslant)$, the reals as a poset, to $\text{Vect}$ or $\text{Vect}_{fr}$, the category of (framed) vector spaces. Filtration function $f:\R^n\to \R$ is assumed to be given.
    • Framed perspective should not be too difficult, just need to find right definitions.
    • Does this give an equivalence of categories (category of persistence modules and category of matchings)? Is that what we want? Do we want to keep only specific properties?
    • Ezra's work is very dense and unpublished. But it seems to have a very precise functoriality (which is not the main thrust of the work, however).
  3. Can the Bubenik-de Silva-Scott interleaving categorification be viewed as a (co)limit? Diagrams are suggestive.
    • Reference is 1707.06288 on the arXiv.
    • Probably not a colimit, because that would be very large, though the arrows suggest a colimit.
    • Have to be careful, because the (co)limit should be in the category of posets, not just interleavings.

New things to learn about:
  1. Algebraic geometry / homotopy theory: the etale space of a sheaf, Kan extensions, model categories, symmetric monoidal categories.
  2. TDA related: Gromov-Hausdorff distance, the universal distance (Michael Lesnick's thesis and papers), merge trees, Reeb graphs, Mapper (the program).

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, a goal not quite achieved. 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)}$.

Note that we have not described what $\mathcal F(U)$ is when $U$ contains stalks with different homotopy types. Omitting this (admittedly large) detail, we have the following:

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)