This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

Parametrized complexes

From Mathematics Is A Science
Redirect page
Jump to navigationJump to search

Since Poincare, homology has been used as the main descriptor of the topology of geometric objects. In the classical context, however, all homology classes receive equal attention. Meanwhile, applications of topology in analysis of images and data have to deal with noise and other uncertainty. This uncertainty appears usually in the form of a real valued function defined on the topological space. Persistence is a measure of robustness of the homology classes of the lower level sets of this function.

Since it's unknown beforehand what is or is not noise in the dataset, we need to capture all homology classes including those that may be deemed noise later. In this chapter we introduce an algebraic structure that contains, without duplication, all these classes. Each of them is associated with its persistence and can be removed when the threshold for acceptable noise is set. The last step can be carried out repeatedly in order to find the best possible threshold. The construction follows the approach to analysis of digital images presented earlier.

The topological spaces subject to such analysis are cell complexes. A cell complex is a combinatorial structure that describes how $k$-dimensional cells are attached to each other along $(k-1)$-dimensional cells. Cell complexes come from the following two main sources.

First, a gray scale image is a real-valued function $f$ defined on a rectangle. Given a threshold $r$, the lower level set $f^{-1}((-\infty,r))$ can be thought of as a binary image. Each black pixel of this image is treated as a square cell in the plane. These $2$-dimensional cells have to be combined with their edges ($1$-cells) and vertices ($0$-cells) while in the $n$-dimensional case the image is decomposed into a combination of $0$-, $1$-, ..., $n$-cubes. This process is called thresholding. The result is a cell complex $K$ for each $r$.

A gray scale image. $\rightarrow$ The gray scale function of the image.

Coins 66 thresholded.jpeg $\rightarrow$ Image decomp 1.jpg

Second, a point cloud is a finite set $S$ in some Euclidean space of dimension $d$. Given a threshold $r$, we deem any two points that lie within $r$ from each other as "close". In this case, this pair of points is connected by an edge. Further, if three points are "close", pairwise, to each other, we add a face spanned by these points. If there are four, we add a tetrahedron, and, finally, any $d+1$ "close" points create a $d$-cell. The process is called the Vietoris-Rips construction. The result is a cell complex $K$ for each $r$.

Point cloud.png $\rightarrow$ Point cloud 3.png Point cloud complex.png

Next, we would like to quantify the topology of the cell complex $K.$ It is done via the Betti numbers of $K$:

  • $B_{0}$ is the number of connected components in $K$;
  • $B_{1}$ is the number of holes or tunnels ($1$ for letter 'O' or the donut; $2$ for letter 'B' and the torus);
  • $B_{2}$ is the number of voids or cavities ($1$ for both the sphere and the torus), etc.

The Betti numbers are computed via homology theory. One starts by considering the collection $C_{k}(K)$ of all formal linear combinations (over a ring $R$) of $k$-cells in $K,$ called $k$-chains.

Point cloud complex with chains.png

Combined they form a finitely generated abelian group called the chain complex $C_{k}(K)$, or collectively $C_{\ast}(K).$ A $k$-chain can be recorded as an $N_{k}$-vector, where $N_{k}$ is the total number of $k$-cells in $K$. The boundary of a $k$-chain is the chain comprised of all $(k-1)$-faces of its cells taken with appropriate signs. Then the boundary operator $\partial:C_{k}(K)\rightarrow C_{k-1}(K),k=0,1,...,$ acts on the chain complex and is represented by a $N_{k}\times N_{k-1}$ matrix.

From the chain complex $C_{\ast}(K),$ the homology group is constructed by means of the standard algebraic tools. To capture the topological features one concentrates on cycles, i.e., chains with zero boundary, $\partial A=0$.

Point cloud complex with cycles.png

Further, one can verify whether two given $k$-cycles $A$ and $B$ are homologous: the difference between them is the boundary of a $(k+1)$-chain $T:A-B=\partial T$ (such as two meridians of the torus). In this case, $A$ and $B$ belong to the same homology class $H=[A]=[B]$.

Torus.JPG

The totality of these equivalence classes in each dimension $k$ is called the $k$-th homology group $H_{k}(K)$ of $K$, collectively $H_{\ast}(K)$. Then, Betti number $B_{k}$ is the rank of $H_{k}(K)$.

The methods for computing homology groups are well developed. In real-life applications however both digital images and point clouds may be noisy and one needs to evaluate the significance of their homology classes. The approach to this problem has been the following. Instead of using a single threshold and studying a single cell complex, one considers all thresholds and all possible cell complexes.

Filtration of coins.png

Point cloud.png Point cloud 1.png Point cloud 2.png Point cloud 3.png Point cloud 4.png Point cloud 5.png

Since increasing threshold $r$ enlarges the corresponding complex, we have a sequence of complexes: $$ K^{1}\hookrightarrow K^{2}\hookrightarrow K^{3}\hookrightarrow K^{4}% \hookrightarrow\ldots\ \hookrightarrow K^{s},$$ where the arrows represent the inclusions: $$i^{n,n+1}:K^{n}\hookrightarrow K^{n+1}.$$ Let $i^{nm}:K^{n}\hookrightarrow K^{m},n\leq m,$ also be the inclusion. This structure $\{K^{n},i^{nm}\}$ is called a filtration.

We illustrate filtrations on the cell level below.

Vietoris-Rips construction:

Filtration example.png

A digital image constructed pixel by pixel:

Stage 1 Stage 2Stage 3 Stage 4

Its homology classes:

Steps 1-4Step 5Step 6 Step 7Step 8Step 9

Now, each of these inclusions generates a homomorphism $i_{\ast}^{nm}:H_{\ast }(K^{n})\rightarrow H_{\ast}(K^{m})$ called the homology map induced by $i^{nm}.$ As a result, we have a sequence of homology groups connected by these homomorphisms: $$H_{\ast}(K^{1})\rightarrow H_{\ast}(K^{2})\rightarrow\ldots\ \rightarrow H_{\ast}(K^{s})\longrightarrow0. $$ These homomorphisms record how the homology changes as the complex grows at each step. For example, a component appears, grows, and then merges with another one, or a hole is formed, shrinks, and then is filled. We refer to these events as birth and death of the corresponding homology class.

In order to evaluate the robustness of an element of one of these groups the persistence of a homology class is defined as the number of steps in the homology sequence it takes for the class to end at $0.$ In other words,

  • persistence = death date - birth date.