TDA

A map\( f : K_1 → K_2\) is called simplicial if it can be described by a vertex map \(g : V(K_1) → V(K_2)\) such that for every simplex \({v_0, . . . , v_k}\) we have\( f({v_0, . . . , v_k}) = {g(v_0), . . . , g(v_k)}\). Since f maps to \(K_2\) we must have that \(f({v_0, . . . , v_k})\) is a simplex in \(K_2\). A simplicial map can also be seen as a map on the underlying spaces \( f : |K_1| → |K_2|.\)

We consider simplicial maps to be the analogue of continuous maps in the world of simplicial complexes.

Place the vertices as distinct points on the moment curve in \(\mathbb{R}^{ 2k+1 }\), which is the curve given by \(f(t) = (t, t^2 , . . . , t^{2k+1} )\). This way, any 2k+2 of the placed points are affinely independent. Thus, any two faces with disjoint vertex sets will not intersect in the realization, showing that the realization is indeed an embedding.

Every k-dimensional simplicial complex has a geometric realization in \(\mathbb{R}^{ 2k+1}\) 

An abstract simplicial complex \(K\) is a family of subsets of a vertex set \(V(K)\) such that if \(τ ∈ K\) and \(σ ⊆ τ\), then \(σ ∈ K\).

A k-simplex in \(\mathbb{R}^d\) is the convex hull of k+1 affinely independent points in \(\mathbb{R}^d\). 

A geometric simplicial complex is a family K of simplices such that

1. if \(τ ∈ K\) and \(σ\) is a face of \(τ\), then \(σ ∈ K\), and

2. for \(σ, τ ∈ K\), their intersection \(σ ∩ τ\) is a face of both.

We first prove this for \(ker(h)\).

1. \(a, b ∈ ker( h) ⇒ h(a) = h(b) = 0\). By definition of homomorphism, \(h(a + b) = h(a) ⋆ h(b) = 0 ⋆ 0 = 0\), and thus by definition of \( ker(h)\), \(a + b ∈ ker(h)\). We conclude that \(ker(h)\) is closed under addition.

2. Associativity follows from associativity of + in G, since \( ker(h) ⊆ G\).

3. \( ∀a ∈ G : h(0) ⋆ h(a) = h(0 + a) = h(a)\), and thus \( h(0) = 0\), from which \(0 ∈ ker(h)\) follows.

4. Let \( a ∈ ker(h)\). Then, \(0 = h(0) = h(a − a) = h(a) ⋆ h(−a) = 0 ⋆ h(−a) = h(−a)\), and thus \(−a ∈ ker(h)\).

A map \(h : G → H\) between abelian groups \( (G, +)\) and \((H, ⋆)\) is a homomorphism if \(h(a + b) = h(a) ⋆ h(b), ∀a, b ∈ G\).

A bijective homomorphism is called an isomorphism.

A group \((G, +) \) is a set \(G\) together with a binary operation “+” such that

1. \(∀a, b ∈ G: a + b ∈ G \)

2. \(∀a, b, c ∈ G: (a + b) + c = a + (b + c)\) (Associativity)

3. \(∃0 ∈ G: a + 0 = 0 + a = a ∀a ∈ G \)

4. \(∀a ∈ G∃ − a ∈ G: a + (−a) = 0 \)

Let \(A ⊆ X\). A deformation retract of \(X\) onto \(A\) is a map \(R : X×[0, 1] → X\), such that

1. \(R(·, 0) = id_X\)

2. \(R(x, 1) ∈ A, ∀x ∈ X\)

3. \(R(a, t) = a, ∀a ∈ A, t ∈ [0, 1]\)

Two spaces \(X, Y\) are homotopy equivalent if there exist maps \(g : X → Y\) and \(h : Y → X\) such that:

1. \(h ◦ g\) is homotopic to \(id_X\) 

2. \(g ◦ h\) is homotopic to \(id_Y\)

or 

\(X, Y\) are homotopy equivalent if and only if there exists a space\( Z\) such that \(X\) and \( Y\) are deformation retracts of \(Z\).

Let \(g, h\) be maps\( X → Y\). A homotopy connecting \(g\) and \(h\) is a map \( H : X × [0, 1] → Y \) such that \(H(·, 0) = g\) and \(H(·, 1) = h.\)

A homeomorphism is a bijective map \(f : X → Y \) whose inverse is also continuous. Two topological spaces are homeomorphic, if there is a homeomorphism between them. We also write \(X ≃ Y\) to say that \( X, Y\) are homeomorphic.

A function \(f : X → Y\) is continuous if for every open set \(U ⊆ Y\), its pre-image \(f^{-1} (U) ⊆ X\)  is open.

1.  The discrete topology \((X, \mathcal{P}(X))\), where \(\mathcal{P}(X)\) denotes the family of all subsets of \(X\). 
2. The trivial topology \((X,(X,\emptyset))\), where the whole set and the empty set are the only opens.
3. The Euclidean space \(X=\mathbb{R}^d\), where the open sets \(T\) are defined as we know from calculus.

A topological space\((X,T)\) is a set of points \(X\), with a system \(T\) of subsets of \(X\) (called the topology on X), such that

1. \( ∅ ∈ T, X ∈ T.\)

2. For every \( S ⊆ T, \cup S ∈ T.\)

3. For every finite \( S ⊆ T, \cap S ∈ T.\) The sets in \(T\) are called the open sets of \(X\).

\textbf{Vectorizations} are methods used to turn persistence diagrams into elements of metric spaces (spaces that have an inner product, e.g. Hilbert space, Euclidean space). Many machine learning pipelines require input points to be in such metric spaces.

General problem: Fragility to outliers; Points in a hole may fill it up prematurely.

Case study:

• \textbf{Dataset structure}: Each vote is encoded as a vector in $\mathbb{R}^{47}$ with values $+1$ for "Yes", $-1$ for "No", and $0$ for absent. PCA shows a square-like structure, where the corners represent typical voting patterns (bipartisan support/rejection, partisan splits) and the center represents ambiguous or absent votes.
• \textbf{Problem}: There are Quorum calls, where both answers (Present/Not present) are coded as 0, so we have at least 3 points exactly in the middle of the square. These points are enough to fill in the 1-dim hole formed by the square's boundary (no 1-dim homology in persistence diagram). => Dataset geometrically resembles a square (which has a hole), persistent homology fails to detect the loop because the middle is "filled in" by outlier points.

Practical Fix:

• Compute the density of each data point, e.g. by using Gaussian kernel density estimation.
• Remove the 1% with lowest density points. 
• Compute persistent homology only on remaining points (high-density points).

=> See homology class with long persistence, reflects the data's geometry.

1. Preprocess: Dataset becomes a high-dimensional point cloud.
2. Subsample: Persistent homology on densest regions shows a circle.
3. Exapand sample: Include medium-density regions, persistent homology shows 5 circles.
4. Full dataset: By including all points, we detect a 2 cycle (Klein bottle structure)

• Sample the densest regions: Large datasize, so we need subsampling. Construct \textbf{Witness complex} on a chosen subset and compute \textbf{persistent homology} in dimensions $0,1,$ and $2$. The resulting barcodes suggest: \begin{itemize}  \item[-]$\beta_0 = 1$: dataset is connected. \item[-]$\beta_1 = 1$: there exists a significant 1-dim hole. \item[-]$\beta_2 = 0$: no significant 2-dim feature.\end{itemize} This tells us, that the point cloud resembles a circle, which is visible via PCA. The circe can be interpreted as the possible angles of a detected "edge" in the images.
• Include medium-density regions: Subsample data with intermediate density and compute the persistent homology. We end up with $\beta_1 = 5$, so 5 1-cycles (high-density: only one 1-cycle). PCA shows cross in the middle of circle seen in high-density subsample, i.e., we see four circles. This leads to interpretation that dataset consists of 3 circles of some $S^2$ that are all orthogonal to one another. One circle representing "edges", one circle describing different translations of horizontal edges, and the third circle describing translations of horizontal edges.
• Include lowest-density regions: When full dataset is considered, we compute $\beta_2=1$, so a nontrivial 2-dim feature and the number of 1-cycles reduces to 2 ($\beta_1=2)$. This space can look like the space of the Klein bottle (we have a 2-cycle with 3 circles)

• Raw data: ca. 4000 grayscale images 
• Patch size: 5000 patches of size 3x3p 
• Filtering: Top 20% most contrasting patches are kept
• Dimensionality: 3x3p patches are flattened to vectors in $\mathbb{R}^9$
• Normalization: 1.) Contrast normalization - set darkest picel to 0, brightest pixel to 1 (affine scaling) 2.) Rescale vector to unit norm (|x| = 1). This gives us a vector on the unit sphere $S^7$.
• Final structure: ca. 4 million points on the unit sphere $S^7$ => Dataset is a large point cloud on $S^7$.

• The \textbf{Hilbert-function} of a pointwise finite dimensional (p.f.d) persistence module $\mathbb{U}$ indexed by $P$ send $p\in P$ to $dim U_p\in \mathbb{N}$. It can be thought of as a 'homological heatmap'.
• The \textbf{rank-invariant} of $\mathbb{U}$ sends a pair $(p,p')$, $p\perceqp'$ to the rank of the map $u_{p,p'}: U_p \rightarrow U_{p'}$, $rank(u_{p,p'}$. Note that two modules with $\mathbb{U} \simeq \mathbb{V}$ have the same rank invariant. For modules indexed by $\mathbb{R}$ this implication also.
• By restricting a bifiltration to a line $L\in\mathbb{R}^2$, where $L : t \mapsto ta + b$ has non negative slope, we get a 1-parameter filtration. The barcode of this restriction is called the \textit{fibered barcode along $L$}. The collection from all such lines forms the \textbf{fibered barcode} of the module. The idea can be extended to lines in $\mathbb{R}^n$.

As we have seen, the persistence modules arising from the Čech or Vietoris-Rips complexes are stable under small perturbations of the underlying data, but not robust.

• Upside: Multiparameter persistence modules are robust to noise and outliers and preserves features that arise from dense clusters of data (greater analytical power). (Robustness
• Downside: Loses simple, complete, and interpretable barcode structure from the 1-parameter case; We can decompose the poset P uniquely into indecomposables, but there is no way to classify or parametrize these indecomposables in general. (Representability)

• \textbf{Degree-Rips bifiltration}: Let $X$ be a finite metric space. Then the family $(\mathbb{VR}^r_d(X))_{r\in\mathbb{R},d\in\mathbb{N}}$ defined above is a filtration indexed by $\mathbb{R}\times \mathbb{N}^{op}$. Notice that $r$ denotes the scale, $d$ denotes the degree. By indexing over $\mathbb{R}\times\mathbb{N}^{op}$, $r$ increases while $d$ decreases. For the single param filtration, the Vietoris-Rips complex is not robust to outliers. The bifiltration counteracts this by introducing a \textbf{density parameter $d$}, which requires that simplices be made of only "dense enough" points. So by indexing over $\mathbb{R}\times \mathbb{N}^{op}$ we get: As $r$ increases, we allow longer edges (i.e. looser geometric structure) while $d$ decreases, allowing points with lower connectivity (i.e. less density). Note: Outliers tend to have low degree, so they are filtered out at high $d$.
• \textbf{Multicover Bifiltration}: Given a finite point cloud $X\subesteq\mathbb{R}^n$, define: \[MC^d_r(X) = \{x\in\mathbb{R}^n\,:\,|B(x,r)\cap X| > d\}.\] This is the union of balls centered at points of $X$ with radius $r$, keeping only those that intersect $> d$ data points. The filtration $(MC_r^d(X))_{(r,d)}$ is also indexed over $\mathbb{R}\times\mathbb{N}^{op}$. This is a density-aware generalization of the Cech filtration. Notice that for large $d$, only regions near densely clustered points survive. So with decreasing $d$, the regions of radius $r$ (increasing) become less dense.
• \textbf{Normalized multicover bifiltrations}: Let $X \subseteq \mathbb{R}^n$ be a finite point cloud. For $r, \rho \in \mathbb{R}$, the sets \[NMC^r_\rho(X) := \{x\in\mathbb{R}^n: |B(x,r)\cap X|\geq \rho|X|\}= \{x\in\mathbb{R}^n:\mu_X(B(x,r)\capX)\geq \rho\}\] form a bifiltration over $\mathbb{R}\times\mathbb{R}^n$ called the \textit{normalized multicover bifiltration.} This persistence module turns out to be stable w.r.t Prohorov distance (i.e. it is stable to outliers). As opposed to the non-normalized version, this bifiltration scales well when wanting to compare datasets of different sizes (MC's density threshold is an absolute count $d\in\mathbb{N}, NMC's density threshold is defined proportionally to the size of the set $\rho|X|$).

For the definition of persistence modules over multiple parameters, we introduce a framework based on \textit{poset-indexed persistence modules}.\\

• \textbf{Poset}: A poset (partially order set) is a tuple $(P, \preceq)$ consisting of a set $P$ and a binary relation $\preceq$ on $P$ satisfying: \begin{itemize} \item $a\preceq a$ for all $a \in P$. \item $a \preceq b$ and $b \preceq a$ implies $a = b$ for all $a,b\in P$. \item $a \preceq b$ and $b \preceq c$ implies $a \preceq c$ for all $a,b,c \in P$. \end{itemize} We will sometimes simply write $P$ if the (partial) ordering $\preceq$ is clear from context.
• \textbf{$P$-filtration}: A $P$-filtration is a family of topological spaces $(X_p)_{p\in P}$ such that: $p\perceq p' \implies X_p \subseteq X_{p'}.$
• \textbf{$P$-Persistence Module}: Given a poset $(P, \perceq)$, a $P$-persistence module over a field $\mathbb{F}$ consists of: \begin{itemize} \item A vector space $U_p$ for each $p\in P$. \item A linear map $u_{p,p'}: U_p \rightarrow U_{p'}$ for all $p\perceq p'$. \item These maps satisfy composition: $u_{p_2,p_3}\circ u_{p_1,p_2}= u_{p_1,p_3} for all $p_1, p_2, p_3 \in P$ with $p_1\perceq p_2\perceq p_3$.

Note: A \textbf{single-parameter} persistence module is a special case of a multiparameter persistence module where the poset is totally ordered (for all $a,b\in P$ either $a\perceq b$ or $b \perceq a$, eg. $(\mathbb{R},\leq)$ is a \textit{totally ordered set}.

see page 85/86

see p. 84/85

Let f : X → Z be well-behaved, and U be a (finite) open cover of Z. Then the Mapper is defined as \(M(\mathcal{U}, f) := N(f ^∗ (\mathcal{U}))\). (N is ther nerve)

Let X, Z be topological spaces. Then we call f : X → Z well-behaved if for all path-connected open sets U ⊆ Z,\( f ^{−1} (U)\) has finitely many path-connected components.

Two Reeb graphs \(R_f\), \(R_g\) are ϵ-interleaved, if there exists a pair of function preserving maps \(φ : R_f → S_ϵ(R_g)\), \(ψ : R_g → S_ϵ(R_f)\) such that the diagram commutes. (see diagram p.82)