TDA
questions tda
questions tda
Fichier Détails
| Cartes-fiches | 63 |
|---|---|
| Langue | Deutsch |
| Catégorie | Mathématiques |
| Niveau | Université |
| Crée / Actualisé | 31.03.2025 / 11.06.2025 |
| Lien de web |
https://card2brain.ch/box/20250331_tda
|
| Intégrer |
<iframe src="https://card2brain.ch/box/20250331_tda/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
graph induced complex
Given two finite point sets Q, P in \( \mathbb{R}^ d\), as well as a graph G(P) with vertices in P, we define v : P → Q by sending each point in P to its closest point in Q. The graph induced complex \(\mathbb{G}(Q, G(P)) \) contains a simplex \( σ = \{q_0, . . . , q_k\} ⊂ Q\) if and only if there is a clique \(\{p_0, . . . , p_k\}\) in G(P) for which \(v(p_i) = q_i\).
parametrized graph induced complex
Let \( G^r (P)\) be the graph on P where pq is an edge if and only if d(p, q) ⩽ 2r. The parameterized graph induced complex \(\mathbb{G}^r (Q, P)\) is defined as \(\mathbb{G}(Q, G^r (P))\).
Bottleneck distance
Let \(Π = \{π : Dgm_p(\mathcal{F}) → Dgm_p(\mathcal{G}) | π \text{ is bijective}\}\) be the set of all bijections between \(Dgm_p(\mathcal{F})\) and \(Dgm_p(\mathcal{G})\). Then, the Bottleneck distance is defined as \(d_b(Dgm_p(\mathcal{F}), Dgm_p(\mathcal{G})) := inf_{π∈Π} sup_{x∈Dgm_p(\mathcal{F})} ||x − π(x)||_\infty\).
Wasserstein distance
For p ⩾ 0, and q ⩾ 1, the q-Wasserstein distance is defined as \(d_{W,q}(Dgm_p(\mathcal{F}), Dgm_p(\mathcal{G})) := [inf_{π∈Π} ( \sum_{ x∈Dgm_p}(\mathcal{F}) (||x − π(x)||_\infty)^q ) ]1/q\)
Stability Theorem for simplicial filtrations
Let \( f, g : K → \mathbb{R}\) be simplex-wise monotone functions. Then, ∀p ⩾ 0 we have \(d_b(Dgm_p(\mathcal{F}_f), Dgm_p(\mathcal{F}_g)) ⩽ ||f − g||_\infty\). Proof/Illustration on p. 62.
persistence module
A persistence module V over \(\mathbb{R}\) is a collection \( V = \{V_a\}_{a∈\mathbb{R}}\) of vector spaces \(V_a\) together with linear maps \(v_{a,a′} : V_a → V_{a′ }\) for a ⩽ a ′ , such that \(v_{a,a} = id\) and\( v_{b,c} ◦ v_{a,b} = v_{a,c}\) for all a ⩽ b ⩽ c.
\(\epsilon\)-interleaving persistence modules
Let U and V be persistence modules over \(\mathbb{R}\) and let ϵ ⩾ 0. We say that U and V are ϵ-interleaved if there exist two families of linear maps, \(φ_a : U_a → V_{a+ϵ}\) and \(ψ_a : V_a → U_{a+ϵ}\) such that the four diagrams are commutative. (diagrams on p.68)
interleaving distance
\(d_I(U, V) := inf\{ϵ | \text{U and V are ϵ-interleaved}\}\)
Theorem bottleneck distance, interleaving distance
If U, V are q-tame persistence modules over \(\mathbb{R}\), then \(d_b(DgmU, DgmV) = d_I(U, V)\)
Hausdorff distance
Let A, B ⊆ X be compact sets. Then the Hausdorff distance between A and B is defined as \(d_H(A, B) := max\{max_{a∈A} d(a, B), max_{ b∈B} d(b, A)\}\).
stability theorem cech complexes
\(d_b(Dgm_p(\mathbb{C}(P)), Dgm_p(\mathbb{C}(Q))) ⩽ d_H(P, Q)\) for all p ⩾ 0. (Proof p.72)
reeb graph
Let X be some topological space, and f a function \(f : X → \mathbb{R}\). Two points x, y are called equivalent (x ∼ y), iff f(x) = f(y) = α and x and y are in the same path-connected component of \(f^{−1} (α)\). The Reeb graph \(R_f \)is the quotient space X/ ∼.
augmented reeb graph
We define the augmented Reeb graph of a simplicial complex with a piecewise-linear-function, as the discretization of the Reeb graph by placing a vertex for every connected component in all the levelsets for the values a for which f(v) = a for some vertex of the simplicial complex.
theorem reeb graphs
Given a simplicial complex K with m faces and a piece-wise linear function \(f : |K| → \mathbb{R}\) on it, we can compute the augmented Reeb graph \(R_f\) of K with respect to f in time O(m log m). (proof p.78)
vertical homology group
The vertical homology group of X with respect to f is the group \(\overset{\vee}{H_p}(X) := H_p(X)/\overline{H_p(X)}\)
horizontal homology group
A p-th homology class \(h ∈ H_p(X)\) is called horizontal if there is a finite set of values \(A = \{a_1, . . . , a_k\}\) such that \( h ∈ im(ι_∗)\) where \( ι_∗\) is the map \(H_p( \bigcup_{ a∈A} X_a) → H_p(X)\) induced by inclusion, where \(X_a = f ^{−1} (a).\)
\(\epsilon-\)thickening
An ϵ-thickening \(X_ϵ \) of some topological space X is given by \(X_ϵ := X × [−ϵ, +ϵ].\)
\(\epsilon\)-smoothing
For a Reeb graph \(R_f\) consider a function\( f_ϵ : (R_f)_ϵ → \mathbb{R}\) such that \((x, t) \mapsto f(x) + t\). The ϵ-smoothing of \(R_f\), denoted by \(S_ϵ(R_f)\) is the Reeb graph of \((R_f)_ϵ\) with regards to \(f_ϵ\).
Reeb graph interleaving
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)
well-behaved
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.
mapper
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)
example mapper
see p. 84/85
mapper algorithm
see page 85/86
