TDA

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)

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.

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)

see p. 84/85

see page 85/86

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}.

• \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|$).

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)

• 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$.

• 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$.

• 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)

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)

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.

\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.

• Persistence statistics: The idea is to summarize the diagram using basic descriptive statistics. For the birth times $b$, death times $d$, the interval points $\frac{b+d}{2}$ and the interval lengths $d-b$, we compute \textbf{means, medians, standard deviations, interquartile ranges,full  ranges, and percentiles (10%,25%,75%,90%)}. We also record the number of bars and entropy. => Output is a vector in $\mathbb{R}^{38}$.
• Persistence landscapes: Intuition: For each point in the persistence diagram draw a horizontal and a vertical line segment to the diagonal. Then flip the arrangement of line segments such that the diagonal is horizontal. We get sth that looks like a mountain range. The persistence landscape is constructed as follows:
  • D = {$(b_1,d_1),...,(b_n,d_n)$} be a persistence diagram, $(b_i,d_i)$ a birth-death pair (off-diagonal point). Each such point gives rise to a triangle defined by the points $\{(t, min[t-b_i,d_i-t]_{+}|t\in\mathbb{R})\}$.
  • The persistence landscape of $D$ is now a function $\lambda_D:\mathbb{N}\times\mathbb{R}\rightarrow \mathbb{R}$ defined by \[\lambda_D(k,t) := \text{ k'-th largest value of }min[t-b_i, d_i -t]\text{ for } i\in \{1,...,n\}.\]
  • For each $k$, we have that $\lambda_D(k, \cdot)$ is a \textit{piece-wise linear function}. This yields a collection of real valued functions, one for each $k$. Notice that for $p=2$, $||\lambda_D||_p$ defines a Hilbert space and thus usable for many ML pipelines.
  • \textit{p-landscape distance $\Lambda_p$} is defined as $\Lambda_p(D_1,D_2):= ||\lambda_{D_1}-\lambda_{D_2}||_p$. Thm.: $D_1, D_2$ persistence diagrams. Then $\Lambda_{\infty}(D_1,D_2)\leq d_b(D_1,D_2)$.
• Betti Curves: Easier way to get piece-wise linear (even constant) functions from a persistence diaram. Defined as the function $\beta : \mathbb{R}\rightarrow\mathbb{N}_{geq 0}$ which assigns each time $t$ the current Betti number of the filtration. => Space of Betti curves is a Hilbert space with the std 2-norm. Note: The Betti curve throws away the pairing between births and deaths, so some topological information is lost.

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 function \(f : X → Y\) is continuous if for every open set \(U ⊆ Y\), its pre-image \(f^{-1} (U) ⊆ X\)  is open.

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.

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.\)

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 \(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]\)

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 \)

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.

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 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.

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

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

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.

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.