2024-09-19

Below is a summary of the current stability results in Steinhaus Filtration and Stable Paths in the Mapper.

---

Recall the Steinhaus filtration ${\text{Nrv}}_{St}(\mathcal{U})$ is defined as the nerve of a cover $\mathcal{U}$ where a simplex $\sigma$ is alive at time $\alpha$ if

$$d_{St}(\{U_i\mid i\in \sigma \})=1-\frac{\mu (\bigcap U_i)}{\mu (\bigcup U_i)}\le \alpha ,$$

i.e., we get a filtered complex

$$K_0\hookrightarrow K_{{\alpha }_1}\hookrightarrow K_{{\alpha }_2}\hookrightarrow \cdots \hookrightarrow K_{{\alpha }_k}\hookrightarrow K_1={\text{Nrv}}_{St}(\mathcal{U})$$

where $K_{\alpha }$ is the subcomplex consisting of simplices whose Steinhaus distance of it’s corresponding covers is at least $\alpha$.

Given two Steinhaus filtrations ${\text{Nrv}}_{St}(\mathcal{U})$ and ${\text{Nrv}}_{St}(\mathcal{V})$, we want to find a condition such that the two filtrations are $ϵ$-interleaving, i.e., some condition $P(ϵ)$ such that under $P(ϵ)$ it follows that for all $i$,

$$d_{St}(V_i)-ϵ\le d_{St}(U_i)\le d_{St}(V_i)+ϵ$$

and

$$d_{St}(U_i)-ϵ\le d_{St}(V_i)\le d_{St}(U_i)+ϵ.$$

The paper constructs a metric, named the bottleneck metric on covers:

Bottleneck metric on covers

Let $\mathcal{U}$ and $\mathcal{V}$ be two finite covers of a finite set $X$ with the same cardinality, and let $\mathcal{M}(\mathcal{U},\mathcal{V})$ be the set of all possible matchings between them. Let $\Delta$ denote the symmetric difference. Then define

$$d_B(\mathcal{U},\mathcal{V})=\underset{M\in \mathcal{M}(\mathcal{U},\mathcal{V})}{\min }\left\{\underset{(U,V)\in M}{\max }\mu (U\Delta V)\right\}.$$

Breakdown of bottleneck metric on covers:

• Given a matching between two covers of equal cardinality, find the pair $(U,V)$ of matched covers such that the measure of $(U\cup V)\setminus (U\cap V)$ is maximal, i.e., the matched pairs of covers with the largest non-overlapping volume.
• For all possible matchings, take the matching that gives the minimal measure as described above.

Theorem 3.5 presents the main stability result on interleaving.

Thm

Suppose that $\mathcal{U}=\{U_i\}$ and $\mathcal{V}=\{V_j\}$ are two covers of $X$ with the same cardinality such that $d_B(\mathcal{U},\mathcal{V})\le \alpha$. Then ${\text{Nrv}}_{St}(\mathcal{U})$ and ${\text{Nrv}}_{St}(\mathcal{V})$ are $\alpha /m$ interleaved where

$$m=\min \left\{\underset{U\in \mathcal{U}}{\min }\mu (U),\underset{V\in \mathcal{V}}{\min }\mu (V)\right\}.$$

Proof: We assume that $\alpha$ is a positive integer and $d_B(\mathcal{U},\mathcal{V})=\alpha$. What is the largest change in Steinhaus distance possible between $U_I$ and $V_J$ where $I$ and $J$ are paired elementwise in a matching? Keep $U_I$ fixed and we try to maximize the change in $\mu (\bigcap U_I)/\mu (\bigcup U_I)$.

Consider taking the symmetric difference of $U_i$ with a set $S_i$ with $\mu (S_i)\le \alpha$. We can partition $S_i$ into two sets $s_{i,1}=U_i\cap S_i$ and $S_{i,2}=S_i\setminus s_{i,1}$. The greatest change to the Steinhaus distance occurs if we can select an $S_i$ for each $U_i$ such that replacing each $U_i$ with $U_i\Delta S_i$ increases or decreases the numerator with $\mu (s_{i,1})$ or $\mu (s_{i,2})$ respectively but does the opposite change to the size of the denominator by $\mu (s_{i,2})$ or $\mu (S_{i,1})$ respectively. In such a case, each change increases or decreases the size of the intersection, and does the opposite to the size of the union. ???

The above paragraph is not clear to me

By Lemma 3.3 and Corollary 3.4, the maximum possible change is achieved when all weight is directed toward increasing or decreasing the size of the intersection. Notice that

$$1-\frac{\mu (\bigcap V_I)+S\alpha }{\mu (\bigcup V_I)}\le 1-\frac{\mu (\bigcap U_I)}{\mu (\bigcup U_I)}\le 1-\frac{\mu (\bigcap V_I)-S\alpha }{\mu (\bigcup V_I)}$$

where $S$ is the cover cardinality.

Thus,

$$\begin{array}{rl}1-\frac{\mu (\bigcap V_I)+S\alpha }{\mu (\bigcup V_I)}& \le 1-\frac{\mu (\bigcap U_I)}{\mu (\bigcup U_I)}\\ \iff 1-\frac{\mu (\bigcap V_I)}{\mu (\bigcup V_I)}-\frac{S\alpha }{\mu (\bigcup V_I)}& \le d_{St}(U_I)\\ \Rightarrow 1-\frac{\mu (\bigcap V_I)}{\mu (\bigcup V_I)}-\frac{S\alpha }{Sm}& \le d_{St}(U_I)\\ \iff d_{St}(V_I)-\frac{\alpha }{m}& \le d_{St}(U_I)\end{array}$$

Likewise,

$$\begin{array}{rl}1-\frac{\mu (\bigcap V_I)-S\alpha }{\mu (\bigcup V_I)}& \ge 1-\frac{\mu (\bigcap U_I)}{\mu (\bigcup U_I)}\\ 1-\frac{\mu (\bigcap V_I)}{\mu (\bigcup V_I)}+\frac{S\alpha }{\mu (\bigcup V_I)}& \ge d_{St}(U_I)\\ \Rightarrow 1-\frac{\mu (\bigcap V_I)}{\mu (\bigcup V_I)}-\frac{S\alpha }{Sm}& \ge d_{St}(U_I)\\ d_{St}(V_I)+\frac{\alpha }{m}& \ge d_{St}(U_I).\end{array}$$

Therefore, ${\text{Nrv}}_{St}(\mathcal{U})$ and ${\text{Nrv}}_{St}(\mathcal{V})$ are $\alpha /m$ interleaved.

Q.E.D.