Department of Statistics, Committee on Computational and Applied Mathematics
The University of Chicago Tianyi Sun and Bradley Nelson [500]Theory of
computation Theory and algorithms for application domains Machine learning
theory Sample complexity and generalization bounds John Q. Open and Joan R.
Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT
2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Greedy Matroid Algorithm And Computational Persistent Homology

Tianyi Sun and Bradley Nelson

###### Abstract

An important problem in computational topology is to calculate the homology of
a space from samples. In this work, we develop a statistical approach to this
problem by calculating the expected rank of an induced map on homology from a
sub-sample to the full space. We develop a greedy matroid algorithm for
finding an optimal basis for the image of the induced map, and investigate the
relationship between this algorithm and the probability of sampling vectors in
the image of the induced map.

###### keywords:

Computational Topology, Greedy Algorithm

##  1 Introduction

A fundamental problem in topological data analysis(TDA) is to estimate the
homology of a space from sub-samples. This problem has been studied in the
past few decades[13, 19, 3, 17]. This problem could be separated into two
steps. One is to determine the number of sub-samples required to see the same
homology as the full point cloud. The other is to determine the size of each
sub-sample where the most important homology of full-space can be obtained.
Estimating homology of a space from samples could be described as determining
topological features of a point cloud from sub-samples. Computing the homology
of a space is useful in various applications such as clustering and cluster
analysis[4, 8, 9, 23, 24, 29], pattern recognition[11, 7], econometrics[33,
10, 14], text[18, 30], and image[15, 6]. Some method has been developed to
improve efficiency of topological tools in the setting of cellular[17].

A variety of solutions have been proposed to homology estimation. Classical
solutions include topological bootstrapping[5], matroid filtrations[17], Morse
theory[21], and estimation of random closed sets[22]. Hausdorff distance is
the distance measure used to evaluate the performance of these estimators. In
this paper we wish to study an estimation approach from a matroid perspective.
Rather than achieving an accurate estimation for the actual shape of a point
cloud, we wish to recover a comprehensive topological properties, i.e., loops
and holes. Our observations, Figure 15 and 16, have shown that minimizing the
Hausdorff distance does not guarantee the quality of the homology estimator.

The motivation for studying the topology of a space comes from the clustering
problem. From a topological perspective, clustering can be viewed as a
question about the homology of the space. The homology of a topological space
$X$ is a set of Abelian groups, denoted by ${H_{0}(X),H_{1}(X),...}$, where
the elements of $H_{0}(X)$ contain information about the connected components
of $X$, and for $k>0$, the group elements of $H_{k}(X)$ contain information
about “cycles” or “holes” of different dimensions. From the perspective of
algebraic topology, the clustering problem is equivalent to recovering
$H_{0}(X)$ where $X$ is a set of point. A statistical perspective of the
recent efforts in TDA has been to extract topological invariants and homology
from random data. The idea is that these topological summaries are useful for
statistical inference and robust under various transformations. Our goal is to
examine homology estimation when the objective is to recover $H_{1}(X)$.

A classical implication for estimate the homology of a space is recovering the
homology of a manifold from a noisy sample and inference the persistent
homology of a function. This problem was previously studied in [1, 27]. Real
world point clouds can be high-dimensional and irregularly structured, for
example, GPT-$2$ output texts point cloud in Figure 2(a). A standard approach
is computing Vietoris–Rips persistence diagram and persistence barcode on full
space. However, for point cloud with large size this approach is too expensive
to compute.

The main objective of this paper is to provide a consistent method for
estimating the homology of a space from samples. A standard approach is
topological bootstrapping[5]. The problem with this approach is that due to
the discrete nature of homology even a tiny error in the set estimate can
introduce an ambiguity in homology. For example, an infinitesimally small
region included by mistake can increase the number of components, while a
small region excluded by mistake might introduce a hole. Such errors in
homology estimation may occur no matter how small the extraneous components
and holes are[2]. This problem is illustrated in Figure 15.

The main result in this work is a robust homology estimation approach of noisy
point clouds. We consider the induced maps between nested pairs of samples,
where the thresholds of Hausdorff distance are fixed $\epsilon>0$. The key
object of interest is the induced maps from sub-samples to full space:

$\mathbf{IM_{n}}:\mathbf{C}(X_{n})\xrightarrow{\epsilon}\mathbf{C}(X_{N}),$

where $n$ is the size of sub-samples and $N$ is the size of full space,
$\mathbf{C}$ is simplicial complex, i.e., Rips complex or chain complex, and
$\mathbf{IM}$ is induced map. Inference of the homology at a single sub-sample
is noisy, however the maps $\mathbf{IM_{n}}$ serves as a filter for the
homological noise. [2] showed that the image of this map is isomorphic to the
homology of the sub-sample.

In this paper, we develop a consistent method to (1) discover the many of sub-
samples needed and (2) the size of these sub-samples to address this problem.
The main idea is a new version of topological bootstrapping[5]. The greedy
matroid algorithm is described in Algorithm 3. In this work, we use two noisy
classical constructions in TDA (Figure 1), Figure-8, and Annulus, to
illustrate the idea. The result stated in Section 5 shows that this method is
more robust than classical solutions in the following aspects:

  * •

Greedy matroid algorithm is computationally more efficient than algorithms of
computing persistence homology, i.e., Vietoris-Rips persistence diagram and
persistence barcode.

  * •

The homology basis computed by our greedy matroid algorithm 3 gives a
comprehensive indication of the basic construction of a given point cloud,
which effectively addresses the ambiguity and the problem of missing
information in the original topological bootstrapping[5].

The paper is structured as follows. In Section 2, we state relevant works to
this project. In Section 3, we state the topological concepts and necessary
definitions used in this paper. Experiments and results are illustrated in
Section 5. In Section 4, we introduce our method and greedy matroid algorithm.
We discuss our results in Section 6. We finally close with a conclusion in
Section 7. Code and additional experiments are available in Appendix 8.

Figure 1: Noisy constructions of Figure-$8$ and Annulus. We compute the
Vietoris-Rips complex, where the distance threshold for rips complex is
$0.25+2*$Hausdorff distance. Point cloud size is 1000 for each construction.
We observe that the homology bases of sub-samples of nearly prefect
constructions are similar, however, the homology bases of sub-samples of noisy
constructions are significantly varied.

##  2 Related Works

In this section, we review relevant works for solving the fundamental problem,
namely computations of persistence homology and topological bootstrapping.

###  2.1 Persistence Homology

A classical approach is directly computing the persistence homology of the
full point cloud using Vietoris-Rips persistence diagram (Figure 2(b)) and
persistence barcode. However, for a point cloud with more than 1000 points,
computing persistence homology using Vietoris-Rips persistence diagram and
persistence barcode is expensive. Other simplicial complexes, i.e., Cech
complex and Delaunay complex, could be an alternative, however, they are even
more expensive to be used to compute.

######  Definition 2.1 (Vietoris-Rips complex[12]).

Let $X=\\{x_{1},x_{2},...,x_{n}\\}$ be a collection of points in
$\mathbb{R}^{d}$, and let $r\geq 0.$ The Vietoris-Rips complex $R(X,r)$ is
constructed as follows:

  * •

The $0$-simplices (vectors) are the points in $X$.

  * •

A $k$-simplex $[x_{i_{0}},...,x_{i_{k}}]$ is in $R(X,r)$ if
$\|x_{i_{j}}-x_{i_{l}}\|\leq r$ for all $0\leq j,$ and $l\leq k$.

###  2.2 Topological Bootstrapping

Another classical approach is topological bootstrapping[5, 32]. However,
topological bootstrapping may detect features that are not important. For
example, the red representative in the noisy construction of Figure-8 in
Figure 2(c), which is not the important representative we are expecting to
detect.

Given a point cloud $\mathcal{X}$, which is too large to be processed
completely. A way of measure the point cloud is through the set of sub-
samples. We can take a sequence of sub-samples
$\mathcal{X}_{1},\cdots,\mathcal{X}_{n}$, where the sizes are small enough to
be efficiently computed on homology through Rips persistence diagram or
persistence barcode to get the persistence homology of each sub-sample.
However, the problem is that are these homology computed from sub-samples the
real homology of the full point cloud? If yes, then $\mathcal{X}$ would have
the same homology as these homology. If no, then there would be two cases need
to be distinguished[5]. One is a single feature is detected repeatedly. The
other is multiple features are detected randomly, but one at a time. If $n$
features are detected in $\mathcal{X}_{i}$ on average, then are we detecting
$n$ features of $\mathcal{X}$ with detection probability equals to $1$, or
$kn$ features with detection probability equals to $\frac{1}{k}$? Therefore,
correlating features across different sub-samples of the full construction is
required. Then here comes the union sequence:

$\mathcal{X}_{1}\rightarrow\mathcal{X}_{1}\cup\mathcal{X}_{2}\leftarrow\mathcal{X}_{2}\rightarrow\dots\leftarrow\mathcal{X}_{n}$

If two samples are sparse, the intersection sequence is not useful, because
they are unlikely to intersect very much.

In this work, the greedy matroid algorithm we developed for finding the
homology basis of a given point cloud is a new version of topological
bootstrapping to tackle the above problems. Instead of computing Rips
persistence diagram or persistence barcode on sub-samples, we compute induced
maps from sub-samples to full point cloud and update the homology basis
iteratively. The homology basis we computed could comprehensively describe the
persistence homology of the given full point cloud.

(a) A point cloud of words of the first $100$ texts in GPT-$2$ outputs
dataset[28] using Word2Vec[20]. The dimension of a word vector is $128$, we
reduced the dimension to $3$ by principle component analysis.

(b) Vietoris - Rips persistence diagram of Figure-8.

(c) Noisy Figure-8. Red, blue, and green lines are detected representatives.

##  3 Background

In this section, we review the concepts, definitions, and propositions used in
this work. For definitions of homology, and computation of induced map, we
refer to Algebraic topology[16] and Parameterized topological data
analysis[25]. For descriptions of matroid and greedy algorithm, we refer to
Matroids and the greedy algorithm[13].

###  3.1 Homology

The input of our greedy matroid algorithm includes a hypothetical homology
basis of the given point cloud and a set of induced maps computed from sub-
samples to the full space.

Homology is a fundamental concept in algebraic topology that provides a way to
study the shape and structure of a space. It associates algebraic objects,
called homology groups, to spaces and maps between them. These groups capture
information about the presence of holes, tunnels, or voids in a space at
different dimensions. The idea behind homology is to capture the essential
topological features of a space by considering cycles and boundaries. In
simple terms, a cycle is a loop or a closed path in the space, while a
boundary is an edge or a path that forms the boundary of a region. The
boundary of a cycle is another cycle, and the homology groups measure the
cycles that are not boundaries, thus capturing the “holes” in the space.

Homology is a functor, which is a mapping between categories. In the context
of algebraic topology, it is a mapping between the category of topological
spaces and the category of algebraic objects (usually groups). The
functoriality of homology means that it preserves the structure and
relationships between spaces and their maps. Specifically, if we have a
continuous map between two spaces, $f:X\rightarrow Y$, the functorality of
homology ensures that there is a corresponding map between their homology
groups, denoted as $f:H(X)\rightarrow H_{*}(Y)$, where $*$ represents the
dimension or degree of the homology groups. This functorial property of
homology is powerful because it allows us to analyze the properties of spaces
and maps by studying the homology groups and their relationships. It enables
us to compare different spaces, detect topological invariants, and understand
how spaces transform under continuous maps.

Homology provides a systematic and algebraic way to study the shape and
structure of spaces, and its functoriality allows us to analyze and compare
spaces using the language of algebraic objects.

######  Definition 3.1 (Simplicial Complexes[16]).

A simplicial complex can be described combinatorially as a set
$\mathcal{X}_{0}$ of vertices together with sets $\mathcal{X}_{n}$ of
$n$-simplices, which are $(n+1)$-element subsets of $\mathcal{X}_{0}$. The
only requirement is that each $(k+1)$-element subset of the vertices of an
$n$-simplex in $\mathcal{X}_{n}$ is a $k$-simplex in $\mathcal{X}_{k}$. From
this combinatorial data a $\delta$-complex $\mathcal{X}$ can be constructed,
once we choose a partial ordering of the vertices $\mathcal{X}_{0}$ that
restricts to a linear ordering on the vertices of each simplex in
$\mathcal{X}_{n}$.

Classical simplicial complexes include Vietoris-Rips complex 2.1, Cech
complex, and Delaunay complex.

######  Definition 3.2 (Chain Complex[25]).

A chain complex is a sequence of vector spaces $\\{C_{k}\\}$, where
$k=0,1,\dots$ with boundary maps $\partial:C_{k}\rightarrow C_{k-1}$ with the
property that $\partial_{k-1}\circ\partial_{k}=0$
In general, $k$ need not start at $0$, which implies $\partial_{0}=0$

$0\leftarrow C_{0}\xleftarrow{\partial_{1}}C_{1}\xleftarrow{\partial_{2}}\dots
C_{k-1}\xleftarrow{\partial_{k}}C_{k}\xleftarrow{\partial_{k+1}}\dots.$

Elements of $C_{k}$ are referred to as $k$-chains, elements of
$\operatorname{ker}\partial_{k}$ are referred to as cycles, and elements of
$\operatorname{img}\partial_{k+1}$ are referred to as boundaries.

A filtration is a nested sequence of spaces

$\mathcal{X}_{0}\subseteq\mathcal{X}_{1}\subseteq\dots\subseteq\mathcal{X}_{n}.$

######  Definition 3.3 (Persistence Homology of Filtrations[25]).

The persistence homology of filtration studies how homology changes through
the sequence of spaces

$\mathcal{H}_{k}(\mathcal{X}_{0})\rightarrow\mathcal{H}_{k}(\mathcal{X}_{1})\rightarrow\dots\rightarrow\mathcal{H}_{k}(\mathcal{X}_{n}).$

######  Definition 3.4 (Homology Revealing Basis[25]).

A homology revealing basis for $\mathcal{C}_{k}$ is a pair
$(\mathcal{B}_{k},\mathcal{I}_{k})$, where $\mathcal{B}_{k}$ is a basis for
$\mathcal{C}_{k}$, and $\mathcal{I}_{k}$ is an index set such that
$\\{b_{i}\in\mathcal{B}_{k}\\}_{i\in\mathcal{I}_{k}}\subseteq\mathcal{B}_{k}$
generates a basis for $\mathcal{H}_{k}(\mathcal{C}_{*})$. Explicitly, a basis
for $\mathcal{H}_{k}$ is

$\\{[b_{i}]|b_{i}\in\mathcal{B}_{k},i\in\mathcal{I}_{k}\\}.$

We use the Reduction Algorithm[25] for computing the homology-revealing basis.
Since the algorithm has been embedded in BATS[26], we call that function
directly for computation.

######  Proposition 3.5.

Given a homology-revealing basis $(\mathcal{B}_{k},\mathcal{I}_{k})$ for
$\mathcal{C}_{k}$, every homology class
$[x]\in\mathcal{H}_{k}(\mathcal{C}_{*})$ has a unique preferred
representative.

We visualized the homology changes through Vietoris-Rips persistence diagram.
The Vietoris-Rips persistence diagram on sub-samples of Figure-8 and Annulus
are in Figure 19 and 20.

Algorithm 1 Computation of Induced Map[25]

Homology representative $\mathbf{x}={U^{C}_{k}}_{i}$ in
$H_{k}(C_{*}),U^{D}_{k},R^{D}_{k+1}$, from reduction algorithm applied to
$\partial_{*}^{D}$, with index set $\mathcal{I}^{D}_{*}$, with index set
$\mathcal{I}^{D}_{k}$. Chain map $\mathcal{F}_{k}$ in original basis.

Induced map on homology, $\tilde{\mathcal{F}_{k}}_{x}$.

$y\leftarrow(U^{D}_{k})^{-1}F_{k}$x

$n\leftarrow\operatorname{dim}D_{k}$

$\tilde{\partial}^{D}_{k+1}\leftarrow(U^{d}_{k})^{-1}R_{k+1}$

for $j=n,n-1,\cdots,1$ do

if $y_{j}$ $\neq 0$ and $j$ is a pivot of column $i$ of
$\tilde{\partial}^{D}_{k+1}$ then

$\alpha\leftarrow\frac{y_{j}}{\tilde{\partial^{D}_{k+1}}_{j,i}}$

$y\leftarrow y-\alpha\tilde{\partial^{D}_{k+1}}_{i}$

end if

end for

(a) Induced map.

(b) Projection map.

Figure 3: Induced map and projection map of Figure-8.

BATS[26] has embedded Algorithm 1 for computing induced map, we directly call
it for computation. The reason of computing induced map, instead of projection
map is that For matrices of induced maps, the column space of induced maps is
the column space of homology of Space 1 in Figure 3. Space 1 is always
different, because sub-samples are different. If we want to apply Kruskal’s
algorithm, we need to have these images to be in the same space. Induced map
is to compute from sub-sample to full space. Projection map is to compute from
full space to sub-sample, it could be used while computing co-homology. The
point is that the image of each single one of the maps should be a consistent
space and the consistent space is the full space that has not been sampled
from. Projection map means that there are more spaces in Space 0s than in
Space 1s, so we cannot induce. But in our case, the Space 0 should be included
in Space 1 in every single case, so we use the induced map.

###  3.2 Greedy Algorithm

The idea of sorting induced maps by how likely they could be the homology
basis of full point cloud is greedy algorithm, i.e., Kruskal’s algorithm.
Kruskal’s algorithm is an algorithm in which we make the optimal step at each
stage in order to find the global optimum. A classical usage of Kruskal’s
algorithm is finding the minimum spanning tree of a graph. The averaged run
time complexity of classical Kruskal’s algorithm is $O(m\operatorname{log}n)$,
where $m$ is the number of edges, and $n$ is the number of vertices. Since we
are dealing with matroids instead of graphs, in Section 4, we adapt the idea
of Kruskal’s algorithm to our case.

######  Definition 3.6.

A matroid $M=(E,I)$ where $E$ is a finite set, and $I$ is a collection of
subsets of $E$, satisfies these axioms:

  * •

$\emptyset\in I$,

  * •

If $A\in I$, and $B\subset A$, then $B\in I$, and

  * •

If $A,B\in I$ and $|A|>|B|$, $\exists x\in A$ such that $B\cup x\in I$.

###  3.3 LU Decomposition

The approach of our choice for checking whether a vector representation of
induced map is in the span of homology basis is LU decomposition with rows and
columns pivoting. We manually implemented this algorithm to adapt it to our
case.

Why use rows and columns pivoting? The induced maps could be
$\begin{bmatrix}0&0&0\\\ 0&1&0\\\ 1&0&0\end{bmatrix}$ or
$\begin{bmatrix}0&1&0\\\ 0&1&0\\\ 0&0&0\end{bmatrix}$. If we only do rows
pivoting, or columns pivoting, or neither of them, we may not form a valid
basis for linear system to determine whether we should include the vector of
induced map or not.

What if forward or backward substitution fail, and/or the linear system is not
solvable? The forward or backward substitution may fail because of the
inconsistent shape of inputs which means that the number of columns of
homology basis and the dimension of induced map are different. Our solution is
returning false, and adding that vector to the basis of homology. If the
linear system is solvable which means that the induced map is in the span of
homology basis, then we don’t include it and eliminate it from consideration.
If the linear system is not solvable which means that the induced map is not
in the span of homology basis, then we add that vector to the basis of
homology.

What if the inputs are sparse matrices? Usually the homology basis is low
dimensional, so we exclude sparse matrix for consideration at this point.

##  4 Greedy Matroid Algorithm

We developed a Greedy Matroid Algorithm 3 to find the comprehensive homology
basis of a space. The input of the algorithm is a list of induced maps. We
first sorted the list based on how likely the vector of an induced map is in
the span of homology basis of the given space by Algorithm 2. Our selection of
criteria is computing the expected rank of a list of induced maps. The list of
ranks represents the list of weights of induced maps. We furthermore created a
dictionary to map each weight to the corresponding induced map and sorted the
induced maps in terms of their weights in decreasing order. Then we
initialized the induced map with the highest weight as the hypothetical
homology basis. The reason is we want to initialize a homology basis that
contains as much information about the full space as possible. Their
rank/weight to some extent represents the amount of information they contain.

Second, we update the basis of homology by iteratively looping into the list
of induced maps and adding the induced maps that were not in the span of
homology basis to the basis. The approach we choose to do this is LU
decomposition with rows and columns pivoting. In practice, we adapt the
classical LU decomposition to accommodate our case in the way mentioned in
section 3. As a result, if the linear system is not solvable or returns a
$False$, which means that the vector of induced map is not in the span of
homology basis, then we include that vector in the basis. If the linear system
is solvable which means the vector of induced map is in the span of the basis
of homology, then we do not include it in the basis and eliminate it from
consideration. Notice that once we add a vector into the homology basis the
dimension of the basis will increase by one. As a result, we should extend the
dimension of the next vector of induced map each time accordingly to ensure
the linear system is valid.

The best case scenario of greedy matroid algorithm 3 is $O(log(n))$, the worst
case scenario is $O(n^{2})$, and the average case scenario is $O(n\cdot
log(n))$.

Figure 4: Vietoris-Rips complexes of both sub-samples and full samples. The
threshold of our choice are $0.25+2*\text{Hausdorff distance}$ respectively.
Algorithm 2 Reduction Algorithm with formation of weights

1:A list of induced maps $\mathcal{IM}$.

2:A list of reduced $\mathcal{IM}$, and a list of corresponding weights
$\mathcal{W}$.

3:for $i=1,\cdots,n$ do

4: for $j=2,\cdots,n$ do

5: if $\mathcal{IM}_{i,j}\neg 0$ then

6: $\mathcal{IM}_{i,j}\leftarrow 1$

7: end if

8: end for

9:end for

10:Initialize weights $\mathcal{W}=[]$

11:for $d=1,\cdots,l_{\mathcal{IM}}$ do

12: Initialize $\mathcal{L}\leftarrow[1,\cdots,l_{\mathcal{IM}_{d}}]$

13: for $i=1,\cdots,l_{\mathcal{IM}_{d}}$ do

14: $j\leftarrow i+1$

15: while $j<l_{\mathcal{IM}_{d}}$ do

16: if $\mathcal{IM}_{d,i}=\mathcal{IM}_{d,j}$ then

17: $\mathcal{L}\leftarrow\mathcal{L}$ remove $j$

18: end if

19: end while

20: end for

21: $\mathcal{W}\leftarrow\mathcal{W};l_{\mathcal{L}}$

22:end for

Algorithm 3 Greedy Matroid Algorithm

1:A list of reduced induced maps $\mathcal{IM}$, and a list of corresponding
weights $\mathcal{W}$.

2:A hypothetical homology basis, $\mathcal{H}$.

3:Initialize a dictionary $\mathcal{D}$, where keys $K\leftarrow\mathcal{IM}$
and values $V\leftarrow\mathcal{W}$ correspondingly.

4:Sort $\mathcal{D}$ in terms of $V$.

5:Initialize $\mathcal{H}\leftarrow K_{1}$, $\mathcal{B}\leftarrow K_{2:}$.

6:Initialize $\mathbf{n_{zeros}}\leftarrow 0$.

7:Solve $\mathcal{H}\mathbf{x}=\mathcal{B}_{1,1}$ for $\mathbf{x}$ by LU
decomposition with rows and columns pivoting.

8:if $\mathbf{x}=$ False or the linear system is unsolvable then

9: $\mathcal{H}\leftarrow\mathcal{H};\mathcal{B}_{1,1}$,
$\mathcal{B}_{1,2}\leftarrow\mathcal{B}_{1,2};0$ or
$\mathcal{B}_{2,1}\leftarrow\mathcal{B}_{2,1};0$,

10: $\mathbf{n_{zeros}}\leftarrow\mathbf{n_{zeros}}+1$

11:end if

12:for $i=1,\cdots,l_{\mathcal{B}}$ do

13: for $j=2,\cdots,l_{\mathcal{B}_{i}}$ do

14: Initialize $\mathbf{b}\leftarrow\mathcal{B}_{i,j}$

15: $\mathbf{b}\leftarrow\mathbf{b};0\times\mathbf{n_{zeros}}$

16: Solve $\mathcal{H}\mathbf{x}=\mathbf{b}$ for $\mathbf{x}$ by LU
decomposition with rows and columns pivoting

17: if $\mathbf{x}$ = False or the linear system is unsolvable then

18: $\mathcal{H}\leftarrow\mathcal{H};\mathcal{B}_{i,j}$

19: $\mathbf{n_{zeros}}\leftarrow\mathbf{n_{zeros}}+1$

20: end if

21: end for

22:end for

##  5 Experiments

We give an example of finding the homology basis of a noisy construction using
Greedy Matroid Algorithm 3. The constructions are noisy Figure-8 and noisy
Annulus. The size of full point cloud is $1000$. The sub-sample sizes are
$20$, $50$, $100$, $300$, $500$, and $800$. For each sub-sample size, we
randomly generated ten sub-samples from the full point cloud and computed
their induced maps.

###  5.1 Induced Maps of Figure-8

The computation of induced maps follows this procedure. We first computed the
Vietoris-Rips complex of sub-samples and full point cloud (Figure 4). Then we
converted it to reduced chain complex and finally computed induced map on it.
The results of induced maps for Figure-8 are in Table 2. To give an example,
while sample size is $50$, the homology values are $H_{0}=1$ and $H_{1}=3$,
then there is one connected component and three loops. We collected induced
maps in Table 2 to a matroid $\mathbf{IM_{fig8-50}}$ as the input of our
greedy matroid algorithm. All inputs are summarized in Table 1.

We convert lists of induced maps of each index to matrices, where row vectors
in a matrix are elements of induced maps and column vectors are elements of
input for greedy matroid algorithm. For empty lists we use zeros to represent.

Indices | Subsample size | TB Homology | $H_{1}$ | $\mathbf{H}$
---|---|---|---|---
0-9 | 20 | $(1,0,...)$ | $\mathbf{IM_{fig8-20}}$ | $\mathbf{H_{20}}$
10-19 | 50 | $(1,3,...)$ | $\mathbf{IM_{fig8-50}}$ | $\mathbf{H_{50}}$
20-29 | 100 | $(2,1,...)$ | $\mathbf{IM_{fig8-100}}$ | $\mathbf{H_{100}}$
30-39 | 300 | $(6,3,...)$ | $\mathbf{IM_{fig8-300}}$ | $\mathbf{H_{300}}$
40-49 | 500 | $(8,7,...)$ | $\mathbf{IM_{fig8-500}}$ | $\mathbf{H_{500}}$
50-59 | 800 | $(12,7,...)$ | $\mathbf{IM_{fig8-800}}$ | $\mathbf{H_{800}}$
Table 1: Figure-8. Induced maps of different sample sizes. Sub-samples were
randomly sampled.

index | size | $H_{1}$
---|---|---
0 | 20 | []
1 | 20 | []
2 | 20 | []
3 | 20 | []
4 | 20 | []
5 | 20 | []
6 | 20 | []
7 | 20 | []
8 | 20 | []
9 | 20 | []

index | size | $H_{1}$
---|---|---
10 | 50 | [[0], [0], [1]]
11 | 50 | [[0, 0], [0, 0], [1, 0]]
12 | 50 | [[0], [0], [2]]
13 | 50 | [[0], [0], [2]]
14 | 50 | [[0, 0], [0, 0], [0, 1]]
15 | 50 | [[0, 0, 0], [0, 0, 0], [2, 2, 0]]
16 | 50 | [[0, 0], [0, 0], [0, 1]]
17 | 50 | [[0], [0], [1]]
18 | 50 | [[0, 0], [0, 0], [2, 0]]
19 | 50 | [[], [], []]

index | size | $H_{1}$
---|---|---
20 | 100 | [[0, 2]]
21 | 100 | [[0, 2]]
22 | 100 | [[0, 2]]
23 | 100 | [[0, 1]]
24 | 100 | [[1, 0, 0]]
25 | 100 | [[2, 0]]
26 | 100 | [[0]]
27 | 100 | [[0, 2]]
28 | 100 | [[0, 1, 0]]
29 | 100 | [[0, 2]]

index | size | $H_{1}$
---|---|---
30 | 300 | [[1, 0, 0],[0, 0, 1],[2, 1, 0]]
31 | 300 | [[0, 1], [2, 0], [0, 0]]
32 | 300 | [[0, 1, 0],[0, 0, 2],[0, 0, 0]]
33 | 300 | [[0, 0, 2, 0],[0, 1, 0, 0],[0, 0, 0, 0]]
34 | 300 | [[0, 2, 0],[2, 0, 0],[0, 0, 0]]
35 | 300 | [[0, 2], [1, 0], [0, 0]]
36 | 300 | [[2, 0], [0, 2], [0, 0]]
37 | 300 | [[2, 0], [0, 2], [0, 0]]
38 | 300 | [[0, 2, 0, 0],[1, 0, 0, 0],[0, 0, 0, 0]]
39 | 300 | [[0, 1, 0, 0],[1, 0, 0, 0],[0, 0, 0, 0]]

index | size | $H_{1}$
---|---|---
40 | 500 | [[0, 0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0], [0, 1, 1, 0, 0, 0, 0],
|  | [0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 2, 0, 2, 0], [1, 2, 0, 1, 0, 0, 0]]
41 | 500 | [[0, 0, 0, 0], [1, 0, 2, 0], [0, 2, 0, 0], [0, 0, 0, 2], [0, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0]]
42 | 500 | [[0, 0, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2], [2, 2, 0, 0], [0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0]]
43 | 500 | [[0, 0, 0], [0, 1, 0], [2, 0, 0], [0, 0, 2], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
44 | 500 | [[0, 0, 0, 0], [0, 1, 0, 0], [2, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
45 | 500 | [[0, 0, 0], [0, 1, 0], [2, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
46 | 500 | [[0, 0, 0, 0], [0, 2, 0, 1], [0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 2], [0, 0, 0, 0]]
47 | 500 | [[0, 0, 0, 0], [0, 2, 0, 0], [1, 0, 0, 0], [0, 0, 2, 2], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
48 | 500 | [[0, 0, 0, 0, 0], [0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 1, 0, 0],
|  | [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
49 | 500 | [[0, 0, 0, 0], [1, 2, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2], [0, 0, 0, 0], [2, 0, 0, 0], [0, 0, 0, 0]]

index | size | $H_{1}$
---|---|---
50 | 800 | [[1, 2, 1, 1, 1, 0, 1], [0, 0, 0, 1, 0, 0, 0], [1, 2, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 2],
|  | [0, 0, 0, 0, 0, 1, 0], [0, 2, 0, 0, 0, 0, 0], [0, 0, 0, 0, 2, 2, 0]]
51 | 800 | [[1, 0, 2, 2], [1, 2, 2, 2], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0]]
52 | 800 | [[0, 0, 1, 1], [0, 2, 0, 0], [2, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [2, 0, 0, 0], [0, 0, 0, 0]]
53 | 800 | [[0, 0, 2, 0, 0], [0, 2, 2, 0, 0], [2, 1, 0, 0, 2], [0, 0, 0, 0, 2],
|  | [0, 0, 0, 0, 0], [2, 1, 0, 1, 2], [0, 0, 0, 0, 0]]
54 | 800 | [[2, 0, 1, 0, 1], [0, 2, 0, 0, 0], [0, 0, 1, 2, 1], [0, 0, 0, 0, 0],
|  | [0, 0, 0, 0, 0],[0, 0, 0, 2, 0], [0, 0, 0, 0, 0]]
55 | 800 | [[2, 1, 2, 0, 0, 0, 1], [0, 0, 2, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 2],
|  | [0, 0, 0, 0, 0, 1, 0], [2, 0, 0, 1, 2, 0, 0], [0, 0, 0, 0, 2, 2, 0]],
56 | 800 | [[1, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 2], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 2], [0, 0, 0, 0]]
57 | 800 | [[1, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 2], [0, 0, 0, 0],
|  | [0, 0, 0, 0], [0, 0, 0, 2], [0, 0, 0, 0]]
58 | 800 | [[0, 0, 2, 0, 0], [0, 2, 2, 0, 0], [2, 1, 0, 0, 2], [0, 0, 0, 0, 2],
|  | [0, 0, 0, 0, 0], [2, 1, 0, 1, 2], [0, 0, 0, 0, 0]]
59 | 800 | [[1, 2, 0, 0], [0, 0, 1, 0],[1, 0, 0, 2], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 2], [0, 0, 0, 0]]

Table 2: Induced maps of Figure-8 from sub-samples of difference sizes to the
full point cloud.

$\mathbf{IM_{fig8-20}}=\begin{Bmatrix}\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{fig8-50}}=\begin{Bmatrix}\begin{bmatrix}&0&\\\ &0&\\\
&1&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &0&0&\\\
&1&0&\end{bmatrix},\begin{bmatrix}&0&\\\ &0&\\\
&2&\end{bmatrix},\begin{bmatrix}&0&\\\ &0&\\\
&2&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &0&0&\\\ &0&1&\end{bmatrix},\\\
\begin{bmatrix}&0&0&0&\\\ &0&0&0&\\\
&2&2&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &0&0&\\\
&0&1&\end{bmatrix},\begin{bmatrix}&0&\\\ &0&\\\
&1&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &0&0&\\\
&2&0&\end{bmatrix},\begin{bmatrix}&0&\\\ &0&\\\
&0&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{fig8-100}}=\begin{Bmatrix}\begin{bmatrix}&0&2&\end{bmatrix},\begin{bmatrix}&0&2&\end{bmatrix},\begin{bmatrix}&0&2&\end{bmatrix},\begin{bmatrix}&0&1&\end{bmatrix},\begin{bmatrix}&1&0&0&\end{bmatrix},\\\
\begin{bmatrix}&2&0&\end{bmatrix},\begin{bmatrix}&0&\end{bmatrix},\begin{bmatrix}&0&2&\end{bmatrix},\begin{bmatrix}&0&1&0&\end{bmatrix},\begin{bmatrix}&0&2&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{fig8-300}}=\begin{Bmatrix}\begin{bmatrix}&1&0&0&\\\ &0&0&1&\\\
&2&1&0&\end{bmatrix},\begin{bmatrix}&0&1&\\\ &2&0&\\\
&0&0&\end{bmatrix},\begin{bmatrix}&0&1&0&\\\ &0&0&2&\\\
&0&0&0&\end{bmatrix},\\\ \begin{bmatrix}&0&0&2&0&\\\ &0&1&0&0&\\\
&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&2&0&\\\ &2&0&0&\\\
&0&0&0&\end{bmatrix},\begin{bmatrix}&0&2&\\\ &1&0&\\\
&0&0&\end{bmatrix},\begin{bmatrix}&2&0&\\\ &0&2&\\\ &0&0&\end{bmatrix},\\\
\begin{bmatrix}&2&0&\\\ &0&2&\\\
&0&0&\end{bmatrix},\begin{bmatrix}&0&2&0&0&\\\ &1&0&0&0&\\\
&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&1&0&0&\\\ &1&0&0&0&\\\
&0&0&0&0&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{fig8-500}}=\begin{Bmatrix}\begin{bmatrix}&0&0&0&0&0&0&1&\\\
&0&1&0&0&0&0&0&\\\ &0&0&0&0&1&0&0&\\\ &0&1&1&0&0&0&0&\\\ &0&0&0&0&0&1&0&\\\
&0&0&0&2&0&2&0&\\\ &1&2&0&1&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\
&1&0&2&0&\\\ &0&2&0&0&\\\ &0&0&0&2&\\\ &0&0&0&0&\\\ &0&0&1&0&\\\
&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\ &0&0&2&0&\\\ &0&0&0&2&\\\
&2&2&0&0&\\\ &0&0&0&0&\\\ &0&1&0&0&\\\ &0&0&0&0&\end{bmatrix},\\\
\begin{bmatrix}&0&0&0&\\\ &0&1&0&\\\ &2&0&0&\\\ &0&0&2&\\\ &0&0&0&\\\
&0&0&0&\\\ &0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\ &0&1&0&0&\\\
&2&0&0&0&\\\ &0&0&1&0&\\\ &0&0&0&0&\\\ &0&0&0&0&\\\
&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&\\\ &0&1&0&\\\ &2&0&0&\\\
&0&0&0&\\\ &0&0&0&\\\ &0&0&0&\\\
&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\ &0&2&0&1&\\\ &0&0&1&0&\\\
&1&0&0&0&\\\ &0&0&0&0&\\\ &0&0&0&2&\\\ &0&0&0&0&\end{bmatrix},\\\
\begin{bmatrix}&0&0&0&0&\\\ &0&2&0&0&\\\ &1&0&0&0&\\\ &0&0&2&2&\\\
&0&0&0&0&\\\ &0&0&0&0&\\\ &0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&0&\\\
&0&1&0&0&0&\\\ &1&0&0&0&0&\\\ &0&0&1&0&0&\\\ &0&0&0&0&0&\\\ &0&0&0&0&0&\\\
&0&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\ &1&2&0&0&\\\ &0&0&2&0&\\\
&0&0&0&2&\\\ &0&0&0&0&\\\ &2&0&0&0&\\\ &0&0&0&0&\end{bmatrix}\end{Bmatrix}$

$\mathbf{IM_{fig8-800}}=\begin{Bmatrix}\begin{bmatrix}&0&0&0&0&0&0&1&\\\
&0&1&0&0&0&0&0&\\\ &0&0&0&0&1&0&0&\\\ &0&1&1&0&0&0&0&\\\ &0&0&0&0&0&1&0&\\\
&0&0&0&2&0&2&0&\\\ &1&2&0&1&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\
&1&0&2&0&\\\ &0&2&0&0&\\\ &0&0&0&2&\\\ &0&0&0&0&\\\ &0&0&1&0&\\\
&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\ &0&0&2&0&\\\ &0&0&0&2&\\\
&2&2&0&0&\\\ &0&0&0&0&\\\ &0&1&0&0&\\\ &0&0&0&0&\end{bmatrix},\\\
\begin{bmatrix}&0&0&0&\\\ &0&1&0&\\\ &2&0&0&\\\ &0&0&2&\\\ &0&0&0&\\\
&0&0&0&\\\ &0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\ &0&1&0&0&\\\
&2&0&0&0&\\\ &0&0&1&0&\\\ &0&0&0&0&\\\ &0&0&0&0&\\\
&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&\\\ &0&1&0&\\\ &2&0&0&\\\
&0&0&0&\\\ &0&0&0&\\\ &0&0&0&\\\
&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\ &0&2&0&1&\\\ &0&0&1&0&\\\
&1&0&0&0&\\\ &0&0&0&0&\\\ &0&0&0&2&\\\ &0&0&0&0&\end{bmatrix},\\\
\begin{bmatrix}&0&0&0&0&\\\ &0&2&0&0&\\\ &1&0&0&0&\\\ &0&0&2&2&\\\
&0&0&0&0&\\\ &0&0&0&0&\\\ &0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&0&\\\
&0&1&0&0&0&\\\ &1&0&0&0&0&\\\ &0&0&1&0&0&\\\ &0&0&0&0&0&\\\ &0&0&0&0&0&\\\
&0&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&\\\ &1&2&0&0&\\\ &0&0&2&0&\\\
&0&0&0&2&\\\ &0&0&0&0&\\\ &2&0&0&0&\\\ &0&0&0&0&\end{bmatrix}.\end{Bmatrix}$

###  5.2 Homology Bases of Figure-8

The estimated matroids of homology basis of noisy Figure-8 computed by Greedy
Matroid Algorithm 3 based on sub-samples of different sizes are below.

$\mathbf{H_{20}}=\begin{bmatrix}&0&\end{bmatrix}$
$\mathbf{H_{50}}=\begin{bmatrix}&0&0&1&\end{bmatrix}$
$\mathbf{H_{100}}=\begin{bmatrix}&1&\end{bmatrix}$
$\mathbf{H_{300}}=\begin{bmatrix}&1&0&1&\\\ &0&0&1&\\\ &0&1&0&\\\
&1&0&0&\end{bmatrix}$

$\mathbf{H_{500}}=\begin{bmatrix}&0&0&0&0&0&0&1&\\\ &0&1&0&1&0&0&1&\\\
&0&0&0&1&0&0&0&\\\ &0&0&0&0&0&1&1&\\\ &0&0&1&0&0&0&0&\\\ &0&0&0&0&1&1&0&\\\
&1&0&0&0&0&0&0&\\\ &0&1&0&0&0&0&0&\\\ &0&1&0&0&0&1&0&\\\
&0&0&0&1&0&1&0&\end{bmatrix}$
$\mathbf{H_{800}}=\begin{bmatrix}&1&0&1&0&0&0&0&\\\ &1&0&1&0&0&1&0&\\\
&1&0&0&0&0&0&0&\\\ &1&1&0&0&0&0&0&\\\ &1&0&1&0&0&0&1&\\\ &0&0&0&0&1&0&1&\\\
&1&0&0&1&0&0&0&\\\ &0&0&0&0&0&1&0&\\\ &0&0&0&0&0&1&1&\\\ &0&0&1&0&0&1&0&\\\
&0&1&1&0&0&1&0&\\\ &0&0&1&1&0&1&0&\\\ &1&1&1&0&0&0&0&\\\ &0&1&0&0&0&0&0&\\\
&1&1&0&0&0&1&0&\end{bmatrix}$

We now show that the estimated homology bases above may or may not be a basis
of Figure-8.

######  Definition 5.1 ([31]).

A matroid $\mathbf{M}$ consists of a non-empty set $\mathbf{E}$, and a
collection $\mathbf{C}$ of non-empty subsets of $\mathbf{E}$ (called cycles)
satisfying the following properties:

  * •

$\mathbf{C}(i)$ no cycle properly contains another cycle;

  * •

$\mathbf{C}(ii)$ if $\mathbf{C_{1}}$ and $\mathbf{C_{2}}$ are two distinct
cycles each containing an element $e$, then exists a cycle in
$\mathbf{C_{1}}\cup\mathbf{C_{2}}$ that does not contain ${e}$.

From Definition 5.1, we could derive the following property:

######  Proposition 5.2 (Basis of Figure-8).

If there are two bases $\mathbf{A}$ and $\mathbf{B}$ in the estimated homology
bases $\mathbf{H}$, such that, $d\cdot\mathbf{A}=0$, $e\cdot\mathbf{B}=0$, and
there is a common vector $h\in\mathbf{A}$ and $h\in\mathbf{B}$, then by
Definition 5.1 there exists a construction of Figure-8 in $\mathbf{H}$.

Algorithm 4 Check Figure-8 Construction

1:$\mathbf{H}$

2:There exists or does not exist a Figure-8 construction in $\mathbf{H}$.

3:for $\mathbf{X},\mathbf{Y}\subset\mathbf{H}$ and
$\mathbf{X},\mathbf{Y}\notin\emptyset$ do

4: if $\mathbf{X}\neq\mathbf{Y}$ and $\mathbf{i}\in\mathbf{X}$ and
$\mathbf{i}\in\mathbf{Y}$ then

5: Solve $\mathbf{X}\mathbf{a}=\mathbf{0}$ and
$\mathbf{Y}\mathbf{c}=\mathbf{0}$ for $\mathbf{a}$ and $\mathbf{c}$ by LU
decomposition with rows and columns pivoting.

6: end if

7:end for

Algorithm 5 Check Annulus Construction

1:$\mathbf{H}$

2:There exists or does not exist an Annulus construction in $\mathbf{H}$.

3:for $\mathbf{X}\subset\mathbf{H}$ and $\mathbf{X}\neq\emptyset$ do

4: Solve $\mathbf{X}\mathbf{a}=\mathbf{0}$ for $\mathbf{a}$ by LU
decomposition with rows and columns pivoting.

5:end for

Since each row represents an element of induced map, here we are checking the
row space. Intuitively, $\mathbf{H_{20}}^{\top}$, $\mathbf{H_{50}}^{\top}$,
and $\mathbf{H_{100}}^{\top}$ does not satisfy the Proposition 5.2.
$\mathbf{H_{300}}^{\top}$ contains two sub-spaces $\begin{bmatrix}&1&1&0&\\\
&0&0&0&\\\ &1&0&1&\end{bmatrix}$ and itself $\begin{bmatrix}&1&0&1&0&\\\
&0&0&0&1&\\\ &1&1&0&0&\end{bmatrix}$. The two matrices could form a cycle and
they have common vectors $\begin{Bmatrix}\begin{bmatrix}&1&\\\ &0&\\\
&1&\end{bmatrix},\begin{bmatrix}&0&\\\ &0&\\\
&1&\end{bmatrix},\begin{bmatrix}&1&\\\ &0&\\\ &0&\end{bmatrix}\end{Bmatrix}$.
Therefore, by Proposition 5.2, $\mathbf{H_{300}}$ could form a construction of
Figure-8, even this is a special case. $\mathbf{H_{500}}^{\top}$ contains
$\begin{bmatrix}&0&0&0&0&\\\ &0&1&0&1&\\\ &0&0&0&0&\\\ &0&1&1&0&\\\
&0&0&0&0&\\\ &0&0&0&0&\\\ &1&1&0&0&\\\ \end{bmatrix}$ and
$\begin{bmatrix}&0&0&0&0&\\\ &0&0&1&1&\\\ &0&0&0&0&\\\ &0&0&0&0&\\\
&0&0&0&0&\\\ &0&1&0&1&\\\ &1&1&0&0&\\\ \end{bmatrix}$ subspaces. Both of the
two contains the common vectors $\begin{Bmatrix}\begin{bmatrix}&0&\\\ &0&\\\
&0&\\\ &0&\\\ &0&\\\ &0&\\\ &1&\\\ \end{bmatrix},\begin{bmatrix}&0&\\\ &1&\\\
&0&\\\ &0&\\\ &0&\\\ &0&\\\ &0&\\\ \end{bmatrix}\end{Bmatrix}$. Therefore, by
Proposition 5.2, $\mathbf{H_{500}}$ could form a construction of Figure-8.
$\mathbf{H_{800}}^{\top}$ contains $\begin{bmatrix}&1&1&0&\\\ &0&0&0&\\\
&1&1&0&\\\ &0&0&0&\\\ &0&0&0&\\\ &0&1&1&\\\ &0&0&0&\\\ \end{bmatrix}$ and
$\begin{bmatrix}&1&1&0&\\\ &1&1&0&\\\ &0&0&0&\\\ &0&0&0&\\\ &0&0&0&\\\
&0&1&1&\\\ &0&0&0&\\\ \end{bmatrix}$ sub-spaces. They contains the common
vector $\begin{Bmatrix}\begin{bmatrix}&0&\\\ &0&\\\ &0&\\\ &0&\\\ &0&\\\
&1&\\\ &0&\\\ \end{bmatrix}\end{Bmatrix}$. Therefore, by Proposition 5.2,
$\mathbf{H_{800}}$ could form a construction of Figure-8. This could be done
by Algorithm 4.

###  5.3 Induced Maps of Noisy Annulus

Indices | Subsample size | IM Homology | $H_{1}$ | $\mathbf{H}$
---|---|---|---|---
0-9 | 20 | $(1,0,...)$ | $\mathbf{IM_{annulus-20}}$ | $\mathbf{H_{annulus-20}}$
10-19 | 50 | $(1,1,...)$ | $\mathbf{IM_{annulus-50}}$ | $\mathbf{H_{annulus-50}}$
20-29 | 100 | $(1,5,...)$ | $\mathbf{IM_{annulus-100}}$ | $\mathbf{H_{annulus-100}}$
30-39 | 300 | $(19,5,...)$ | $\mathbf{IM_{annulus-300}}$ | $\mathbf{H_{annulus-300}}$
40-49 | 500 | $(2,6,...)$ | $\mathbf{IM_{annulus-500}}$ | $\mathbf{H_{annulus-500}}$
50-59 | 800 | $(2,6,...)$ | $\mathbf{IM_{annulus-800}}$ | $\mathbf{H_{annulus-800}}$
Table 3: Annulus. Induced maps of different sample sizes. Sub-samples were
randomly sampled.

index | size | $H_{1}$
---|---|---
0:20 | 20 | []
20:40 | 20 | []
40:60 | 20 | []
60:80 | 20 | []
80:100 | 20 | []
120:140 | 20 | []
140:160 | 20 | []
160:180 | 20 | []
180:200 | 20 | []
200:220 | 20 | []

index | size | $H_{1}$
---|---|---
0:50 | 50 | [[0, 0, 0, 2, 0, 0]]
50:100 | 50 | [[0, 0]]
100:150 | 50 | [[0, 0]]
150:200 | 50 | [[]]
200:250 | 50 | [[0]]
250:300 | 50 | [[0]]
300:350 | 50 | [[0]]
350:400 | 50 | [[]]
400:450 | 50 | [[0]]
450:500 | 50 | [[0]]

index | size | $H_{1}$
---|---|---
0:100 | 100 | [[0, 0, 0, 0, 2, 0, 0, 0, 0, 1],[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
|  | [0, 0, 0, 0, 0, 2, 0, 0, 0, 0],[0, 0, 0, 0, 0, 2, 0, 0, 0, 0]]
100:200 | 100 | [[0, 1, 0], [0, 2, 0], [1, 0, 0], [0, 0, 0], [0, 0, 0]]
200:300 | 100 | [[2], [1], [2], [0], [0]]
300:400 | 100 | [[1], [2], [1], [0], [0]]
400:500 | 100 | [[1], [2], [1], [0], [0]]
500:600 | 100 | [[1], [2], [1], [0], [0]]
600:700 | 100 | [[1], [2], [1], [0], [0]]
700:800 | 100 | [[2], [1], [2], [0], [0]]
800:900 | 100 | [[1], [2], [1], [0], [0]]
900:1000 | 100 | [[1], [2], [1], [0], [0]]

index | size | $H_{1}$
---|---|---
0:300 | 300 | [[0, 0, 2, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 2], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0]]
100:400 | 300 | [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
200:500 | 300 | [[2], [0], [0], [0], [0]]
300:600 | 300 | [[1, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
400:700 | 300 | [[0, 0, 2, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
500:800 | 300 | [[2], [0], [0], [0], [0]]
600:900 | 300 | [[1, 0], [0, 0], [0, 0], [0, 0], [0, 0]]
700:1000 | 300 | [[0, 1], [0, 0], [0, 0], [0, 0], [0, 0]]
250:550 | 300 | [[1, 0], [0, 0], [0, 0], [0, 0], [0, 0]]
550:850 | 300 | [[2], [0], [0], [0], [0]]

index | size | $H_{1}$
---|---|---
0:500 | 500 | [[0, 0, 0, 0, 0, 1], [2, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0],
|  | [1, 2, 2, 2, 2, 0], [0, 2, 0, 0, 2, 0], [0, 2, 0, 0, 0, 0]]
100:600 | 500 | [[0, 0], [1, 0], [2, 0], [2, 2], [0, 0], [0, 0]]
200:700 | 500 | [[0, 0], [1, 0], [2, 0], [2, 1], [0, 0], [0, 0]]
300:800 | 500 | [[0], [1], [2], [2], [0], [0]]
400:900 | 500 | [[0], [1], [2], [2], [0], [0]]
500:1000 | 500 | [[0], [2], [1], [1], [0], [0]]
450:950 | 500 | [[0], [2], [1], [1], [0], [0]]
350:850 | 500 | [[0], [1], [2], [2], [0], [0]]
250:750 | 500 | [[0], [2], [1], [1], [0], [0]]
150:650 | 500 | [[0, 0], [2, 0], [1, 0], [1, 1], [0, 0], [0, 0]]

index | size | $H_{1}$
---|---|---
0:800 | 800 | [[0, 0, 0, 0, 0, 1], [2, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0],
|  | [1, 2, 2, 2, 2, 0], [0, 2, 0, 0, 2, 0], [0, 2, 0, 0, 0, 0]]
100:900 | 800 | [[0, 0], [1, 0], [2, 0], [2, 2], [0, 0], [0, 0]]
200:1000 | 800 | [[0, 0], [1, 0], [2, 0], [2, 1], [0, 0], [0, 0]]
50:850 | 800 | [[0, 0, 0, 0, 0, 0],[0, 0, 1, 1, 0, 0],[0, 0, 2, 2, 1, 1],
|  | [0, 0, 0, 2, 0, 0],[0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0]]
150:950 | 800 | [[0, 0], [2, 0], [1, 0], [1, 1], [0, 0], [0, 0]]
20:820 | 800 | [[0, 0, 0, 0, 0],[0, 1, 0, 2, 0],[0, 2, 1, 1, 0],[0, 2, 0, 0, 2],[0, 0, 0, 0, 2],[0, 0, 0, 0, 0]]
120:920 | 800 | [[0, 0], [1, 0], [2, 0], [2, 1], [0, 0], [0, 0]]
130:930 | 800 | [[0, 0], [2, 0], [1, 0], [1, 1], [0, 0], [0, 0]]
40:840 | 800 | [[0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 2], [0, 2, 0, 0, 1, 0],
|  | [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
140:940 | 800 | [[0, 0], [1, 1], [2, 2], [2, 0], [0, 0], [0, 0]]

Table 4: Annulus. Induced maps from sub-samples to full point cloud of size
$1000$. Sub-samples were randomly chosen from the full point cloud.

$\mathbf{IM_{annulus-20}}=\begin{Bmatrix}\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{annulus-50}}=\begin{Bmatrix}\begin{bmatrix}&0&0&0&2&0&0&\end{bmatrix},\begin{bmatrix}&0&0&\end{bmatrix},\begin{bmatrix}&0&0&\end{bmatrix},\\\
\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&0&\end{bmatrix},\begin{bmatrix}&0&\end{bmatrix},\begin{bmatrix}&0&\end{bmatrix},\begin{bmatrix}&\end{bmatrix},\begin{bmatrix}&0&\end{bmatrix},\begin{bmatrix}&0&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{annulus-100}}=\begin{Bmatrix}\begin{bmatrix}&0&2&0&1&\\\
&0&1&0&0&\\\ &1&0&0&0&\\\ &0&0&2&0&\\\
&0&0&2&0&\end{bmatrix},\begin{bmatrix}&0&1&0&\\\ &0&2&0&\\\ &1&0&0&\\\
&0&0&0&\\\ &0&0&0&\end{bmatrix},\begin{bmatrix}&2&\\\ &1&\\\ &2&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&1&\\\ &2&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix},\\\ \begin{bmatrix}&1&\\\ &2&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&1&\\\ &2&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&1&\\\ &2&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&2&\\\ &1&\\\ &2&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&1&\\\ &2&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&1&\\\ &2&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{annulus-300}}=\begin{Bmatrix}\begin{bmatrix}&0&0&2&0&0&\\\
&0&0&0&0&0&\\\ &0&0&0&0&2&\\\ &0&1&0&0&0&\\\
&0&0&0&1&0&\end{bmatrix},\begin{bmatrix}&1&0&0&0&\\\ &0&0&0&0&\\\ &0&0&0&0&\\\
&0&0&0&0&\\\ &0&0&0&0&\end{bmatrix},\begin{bmatrix}&2&\\\ &0&\\\ &0&\\\ &0&\\\
&0&\end{bmatrix},\\\ \begin{bmatrix}&1&0&0&\\\ &0&0&0&\\\ &0&0&0&\\\
&0&0&0&\\\ &0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&2&0&\\\ &0&0&0&0&\\\
&0&0&0&0&\\\ &0&0&0&0&\\\ &0&0&0&0&\end{bmatrix},\begin{bmatrix}&2&\\\ &0&\\\
&0&\\\ &0&\\\ &0&\end{bmatrix},\\\ \begin{bmatrix}&1&0&\\\ &0&0&\\\ &0&0&\\\
&0&0&\\\ &0&0&\end{bmatrix},\begin{bmatrix}&0&1&\\\ &0&0&\\\ &0&0&\\\ &0&0&\\\
&0&0&\end{bmatrix},\begin{bmatrix}&1&0&\\\ &0&0&\\\ &0&0&\\\ &0&0&\\\
&0&0&\end{bmatrix},\begin{bmatrix}&2&\\\ &0&\\\ &0&\\\ &0&\\\
&0&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{annulus-500}}=\begin{Bmatrix}\begin{bmatrix}&0&0&0&0&0&1&\\\
&2&0&0&1&0&0&\\\ &1&0&0&0&0&0&\\\ &1&2&2&2&2&0&\\\ &0&2&0&0&2&0&\\\
&0&2&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &1&0&\\\ &2&0&\\\ &2&2&\\\
&0&0&\\\ &0&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &1&0&\\\ &2&0&\\\ &2&1&\\\
&0&0&\\\ &0&0&\\\ \end{bmatrix},\begin{bmatrix}&0&\\\ &1&\\\ &2&\\\ &2&\\\
&0&\\\ &0&\end{bmatrix},\\\ \begin{bmatrix}&0&\\\ &1&\\\ &2&\\\ &2&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&0&\\\ &2&\\\ &1&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&0&\\\ &2&\\\ &1&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&0&\\\ &1&\\\ &2&\\\ &2&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&0&\\\ &2&\\\ &1&\\\ &1&\\\ &0&\\\
&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &2&0&\\\ &1&0&\\\ &1&1&\\\ &0&0&\\\
&0&0&\end{bmatrix}\end{Bmatrix}$.

$\mathbf{IM_{annulus-800}}=\begin{Bmatrix}\begin{bmatrix}&0&0&0&0&0&1&\\\
&2&0&0&1&0&0&\\\ &1&0&0&0&0&0&\\\ &1&2&2&2&2&0&\\\ &0&2&0&0&2&0&\\\
&0&2&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &1&0&\\\ &2&0&\\\ &2&2&\\\
&0&0&\\\ &0&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &1&0&\\\ &2&0&\\\ &2&1&\\\
&0&0&\\\ &0&0&\end{bmatrix},\\\ \begin{bmatrix}&0&0&0&0&0&0&\\\
&0&0&1&1&0&0&\\\ &0&0&2&2&1&1&\\\ &0&0&0&2&0&0&\\\ &0&0&0&0&0&0&\\\
&0&0&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &2&0&\\\ &1&0&\\\ &1&1&\\\
&0&0&\\\ &0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&0&\\\ &0&1&0&2&0&\\\
&0&2&1&1&0&\\\ &0&2&0&0&2&\\\ &0&0&0&0&2&\\\ &0&0&0&0&0&\end{bmatrix},\\\
\begin{bmatrix}&0&0&\\\ &1&0&\\\ &2&0&\\\ &2&1&\\\ &0&0&\\\
&0&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &2&0&\\\ &1&0&\\\ &1&1&\\\ &0&0&\\\
&0&0&\end{bmatrix},\begin{bmatrix}&0&0&0&0&0&0&\\\ &0&0&0&1&0&2&\\\
&0&2&0&0&1&0&\\\ &0&0&1&0&0&0&\\\ &0&0&0&0&0&0&\\\
&0&0&0&0&0&0&\end{bmatrix},\begin{bmatrix}&0&0&\\\ &1&1&\\\ &2&2&\\\ &2&0&\\\
&0&0&\\\ &0&0&\end{bmatrix}\end{Bmatrix}$.

###  5.4 Homology Basis of Annulus

The estimated homology basis of noisy annulus computed by our algorithm is
listed below.

$\mathbf{H_{annulus-20}}=\begin{bmatrix}&\end{bmatrix}$
$\mathbf{H_{annulus-50}}=\begin{bmatrix}&1&\end{bmatrix}$
$\mathbf{H_{annulus-100}}=\begin{bmatrix}&0&0&1&0&0&\\\ &1&1&0&0&0&\\\
&0&0&0&1&1&\\\ &1&0&0&0&0&\\\ &1&1&1&0&0&\end{bmatrix}$

$\mathbf{H_{annulus-300}}=\begin{bmatrix}&0&0&0&1&0&\\\ &1&0&0&0&0&\\\
&0&0&0&0&1&\\\ &0&0&1&0&0&\end{bmatrix}$
$\mathbf{H_{annulus-500}}=\begin{bmatrix}&0&1&1&1&0&0&\\\ &0&0&0&1&1&1&\\\
&0&0&0&1&0&0&\\\ &0&1&0&1&0&0&\\\ &0&0&0&1&1&0&\\\ &1&0&0&0&0&0&\end{bmatrix}$

$\mathbf{H_{annulus-800}}=\begin{bmatrix}&0&1&1&1&0&0&\\\ &0&0&0&1&1&1&\\\
&0&0&0&1&0&0&\\\ &0&1&0&1&0&0&\\\ &0&0&0&1&1&0&\\\ &1&0&0&0&0&0&\\\
&0&1&1&0&0&0&\\\ &0&0&1&0&0&0&\\\ &0&1&0&0&0&0&\end{bmatrix}$

Similarly, From Definition 5.1, we could derive the following property for
Annulus.

######  Proposition 5.3 (Basis of Annulus).

If there is a subspace $\mathbf{A}$ in the estimated homology space
$\mathbf{H}$, such that, $d\cdot\mathbf{A}=0$, then by Definition 5.1 there
exists a construction of Annulus in $\mathbf{H}$.

Since each row represents an element of induced map, we are checking the row
spaces. Intuitively, $\mathbf{H_{20}}^{\top}$ and $\mathbf{H_{50}}^{\top}$
does not satisfy the condition of the above property.
$\mathbf{H_{100}}^{\top}$ contains a subspace $\begin{bmatrix}&0&1&1&\\\
&0&1&1&\\\ &1&0&1&\\\ &0&0&0&\\\ &0&0&0&\end{bmatrix}$. Therefore, by
Proposition 5.3, $\mathbf{H_{100}}^{\top}$ could form a construction of
Annulus. Intuitively, $\mathbf{H_{300}}^{\top}$ is linearly independent, so it
forms a Forest and doesn’t form a cycle. Therefore, $\mathbf{H_{300}}^{\top}$
cannot be a representation of Annulus. $\mathbf{H_{500}}^{\top}$ is in the
same situation. $\mathbf{H_{800}}^{\top}$ contains a subspace
$\begin{bmatrix}&0&0&0&0&0&\\\ &1&1&1&1&0&\\\ &1&0&1&0&1&\\\ &1&1&0&0&0&\\\
&0&0&0&0&0&\\\ &0&0&0&0&0&\end{bmatrix}$. Therefore, by Proposition 5.3,
$\mathbf{H_{800}}^{\top}$ could form a construction of Annulus. This could be
done by Algorithm 5.

##  6 Discussion

Indices | Subsample size | RC speed (seconds) | GMA speed (seconds)
---|---|---|---
0-9 | 20 | 28.352442026138306 | 0.0018012523651123047
10-19 | 50 | 17.811870098114014 | 0.002874135971069336
20-29 | 100 | 8.287723064422607 | 0.0024347305297851562
30-39 | 300 | 2.054633855819702 | 0.004442691802978516
40-49 | 500 | 1.607776165008545 | 0.007197856903076172
50-59 | 800 | 0.7690119743347168 | 0.008867025375366211

Table 5: Figure-8. Average speed of computation using Rips persistence
diagram(RC) and greedy matroid algorithm(GMA).

Indices | Subsample size | RC speed (seconds) | GMA speed (seconds)
---|---|---|---
0-9 | 20 | 56.045454263687134 | 0.0025789737701416016
10-19 | 50 | 15.729853868484497 | 0.0007250308990478516
20-29 | 100 | 6.515740871429443 | 0.0009210109710693359
30-39 | 300 | 0.5750489234924316 | 0.0013933181762695312
40-49 | 500 | 0.1607518196105957 | 0.00101470947265625
50-59 | 800 | 0.05244708061218262 | 0.0011279582977294922

Table 6: Annulus. Average speed of computation using Rips persistence
diagram(RC) and greedy matroid algorithm(GMA).

Indices | Subsample size | Homology by TB | Homology by GMA | Target Homology
---|---|---|---|---
0-9 | 20 | $(1,0,...)$ | $(0,0,...)$ | $(1,2,...)$
10-19 | 50 | $(1,3,...)$ | $(1,0,...)$ | $(1,2,...)$
20-29 | 100 | $(2,1,...)$ | $(1,0,...)$ | $(1,2,...)$
30-39 | 300 | $(6,3,...)$ | $(1,2,...)$ | $(1,2,...)$
40-49 | 500 | $(8,7,...)$ | $(1,2,...)$ | $(1,2,...)$
50-59 | 800 | $(12,7,...)$ | $(1,2,...)$ | $(1,2,...)$

Table 7: Figure-8. Persistence Homology computed by topological
bootstrapping(TB) and greedy matroid algorithm(GMA).

Indices | Subsample size | Homology by TB | Homology by GMA | Target Homology
---|---|---|---|---
0-9 | 20 | $(1,0,...)$ | $(0,0,...)$ | $(0,1,...)$
10-19 | 50 | $(1,1,...)$ | $(1,0,...)$ | $(0,1,...)$
20-29 | 100 | $(1,5,...)$ | $(0,1,...)$ | $(0,1,...)$
30-39 | 300 | $(19,5,...)$ | $(3,0,...)$ | $(0,1,...)$
40-49 | 500 | $(2,6,...)$ | $(3,0,...)$ | $(0,1,...)$
50-59 | 800 | $(2,6,...)$ | $(0,1,...)$ | $(0,1,...)$

Table 8: Annulus. Persistence Homology computed by topological
bootstrapping(TB) and greedy matroid algorithm(GMA).

We computed the speed of computing persistence homology using Vietoris-Rips
reduced Chain complex and greedy matroid algorithm. The results, Table 8 and
Table 8, show that our greedy matroid algorithm is faster than Rips
persistence diagram. We compared the homology values, $H_{0}$ and $H_{1}$,
computed by our greedy matroid algorithm and topological bootstrapping. The
results, Table 8 and Table 8, show that homology values computed by our greedy
matroid algorithm are more accurate than homology values computed by
topological bootstrapping.

##  7 Conclusion

The greedy matroid algorithm speeds up computing persistence homology. It
provides an efficient way of computing the homology basis of sub-samples and
inducing homology basis of the full space from sub-samples. Our algorithm is
computationally more efficient than algorithms of computing persistence
homology, i.e., Vietoris-Rips persistence diagram and persistence barcode.

The accuracy of homology values, $H_{0}$ and $H_{1}$, computed by greedy
matroid algorithm is higher than $H_{0}$ and $H_{1}$ computed by topological
bootstrapping. Thus, our greedy matroid algorithm effectively addresses the
ambiguity problem in topological bootstrapping.

Our algorithm gives a comprehensive indication of the basic construction of a
given point cloud, which could not be achieved by computing Vietoris–Rips
persistence diagram, persistence barcode, and topological bootstrapping.

We will continue to test our method on three dimensional constructions. As we
observed that the estimated bases of construction depend on the threshold of
Vietoris-Rips complex, we will explore how to determine the optimum threshold.

## Acknowledgement

We thank the support of DARPA research.

## References

  * [1] Sivaraman Balakrishnan, Alesandro Rinaldo, Don Sheehy, Aarti Singh, and Larry Wasserman.  Minimax rates for homology inference.  In Neil D. Lawrence and Mark Girolami, editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pages 64–72, La Palma, Canary Islands, 21–23 Apr 2012. PMLR.
  * [2] Omer Bobrowski, Sayan Mukherjee, and Jonathan E. Taylor.  Topological consistency via kernel estimation.  Bernoulli, 2017.
  * [3] Allan Borodin, Morten N Nielsen, and Charles Rackoff.  (incremental) priority algorithms.  Algorithmica, 37:295–326, 2003.
  * [4] Cora Brown, Sarah Milstein, Tianyi Sun, and Cooper Zhao.  Clustering us counties to find patterns related to the covid-19 pandemic.  arXiv preprint arXiv:2303.11936, 2023.
  * [5] Gunnar Carlsson and Vin de Silva.  Zigzag persistence.  Foundations of Computational Mathematics, page 10(4):367–405, 2010\.
  * [6] James R Clough, Nicholas Byrne, Ilkay Oksuz, Veronika A Zimmer, Julia A Schnabel, and Andrew P King.  A topological loss function for deep-learning based image segmentation using persistent homology.  IEEE transactions on pattern analysis and machine intelligence, 44(12):8766–8778, 2020.
  * [7] Antonio Cuevas.  On pattern analysis in the non-convex case.  Kybernetes, 19(6):26–33, 1990.
  * [8] Antonio Cuevas, Manuel Febrero, and Ricardo Fraiman.  Estimating the number of clusters.  The Canadian Journal of Statistics / La Revue Canadienne de Statistique, 28(2):367–382, 2000.
  * [9] Antonio Cuevas, Manuel Febrero, and Ricardo Fraiman.  Cluster analysis: a further approach based on density estimation.  Computational Statistics & Data Analysis, 36(4):441–459, 2001\.
  * [10] Dominique Deprins and Léopold Simar.  On farrell measures of technical efficiency.  Recherches Économiques de Louvain/Louvain Economic Review, 49(2):123–137, 1983.
  * [11] Luc Devroye and Gary L Wise.  Detection of abnormal behavior via nonparametric estimation of the support.  SIAM Journal on Applied Mathematics, 38(3):480–488, 1980.
  * [12] Herbert Edelsbrunner.  The union of balls and its dual shape.  In Proceedings of the Ninth Annual Symposium on Computational Geometry, SCG ’93, page 218–231, New York, NY, USA, 1993. Association for Computing Machinery.
  * [13] Jack Edmonds.  Matroids and the greedy algorithm.  Mathematical programming, 1:127–136, 1971.
  * [14] Michael James Farrell.  The measurement of productive efficiency.  Journal of the Royal Statistical Society Series A: Statistics in Society, 120(3):253–281, 1957.
  * [15] Zhenqi Fu, Huangxing Lin, Yan Yang, Shu Chai, Liyan Sun, Yue Huang, and Xinghao Ding.  Unsupervised underwater image restoration: From a homology perspective.  In Proceedings of the AAAI Conference on Artificial Intelligence, pages 643–651, 2022.
  * [16] Allen Hatcher.  Algebraic topology.  Cambridge University Press, 2002.
  * [17] Gregory Henselman and Robert Ghrist.  Matroid filtrations and computational persistent homology.  arXiv preprint arXiv:1606.00199, 2016.
  * [18] Firas A Khasawneh and Elizabeth Munch.  Stability determination in turning using persistent homology and time series analysis.  In ASME International Mechanical Engineering Congress and Exposition, volume 46483, page V04BT04A038. American Society of Mechanical Engineers, 2014.
  * [19] Eugene L Lawler.  Combinatorial optimization: networks and matroids.  Courier Corporation, 2001.
  * [20] Tomas Mikolov, Kai Chen, Gregory S. Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  In International Conference on Learning Representations, 2013.
  * [21] Konstantin Mischaikow and Vidit Nanda.  Morse theory for filtrations and efficient computation of persistent homology.  Discrete & Computational Geometry, 50:330–353, 2013.
  * [22] Ilya S Molchanov.  Empirical estimation of quantiles of distributions of random closed sets.  Teoriya Veroyatnostei i ee Primeneniya, 35(3):586–592, 1990.
  * [23] Dietrich Werner Müller.  The excess mass approach in statistics.  Heidelberg, 1992.
  * [24] Dietrich Werner Müller and Günther Sawitzki.  Excess mass estimates and tests for multimodality.  Journal of the American Statistical Association, 86(415):738–746, 1991.
  * [25] Bradley J Nelson.  Parameterized topological data analysis.  Ph.D. dissertation, Stanford University, 2020.
  * [26] Bradley J Nelson.  Bats.  Software available at https://bats-tda.readthedocs.io/en/latest/index.html, 2021.
  * [27] Partha Niyogi, Stephen Smale, and Shmuel Weinberger.  A topological view of unsupervised learning from noisy data.  SIAM J. Comput., 40:646–663, 2011.
  * [28] OpenAI.  gpt-2-output-dataset.  Dataset available at https://github.com/openai/gpt-2-output-dataset, 2021.
  * [29] Wolfgang Polonik.  Measuring mass concentrations and estimating density contour clusters-an excess mass approach.  The annals of Statistics, pages 855–881, 1995.
  * [30] B. Rieck and H. Leitte.  Structural analysis of multivariate point clouds using simplicial chains.  Computer Graphics Forum, 33(8):28–37, 2014.
  * [31] Man-Keung Siu.  Introduction to graph theory , by robin j. wilson. pp. 171.£ 14.99. 1996. isbn: 0-582-24993-7 (longman).  The Mathematical Gazette, 82(494):343–344, 1998.
  * [32] Andrew Tausz.  Extensions and Applications of Persistence Based Algorithms in Computational Topology.  Ph.D. dissertation, Stanford University, 2012.
  * [33] Henry Tulkens and Parkash Chander.  Public goods, environmental externalities and fiscal competition.  Springer, 2006.

##  8 Appendix

The code is available at https://github.com/tianyisuntt/sampling.

(a) Expected rank of induced maps of Figure-8.

(b) Expected rank of induced maps of Annulus.

Figure 5: Rank statistics. $\mathbf{y}$-axis is the number of ranks and
$\mathbf{x}$-axis is the number of samples.

###  8.1 Induced Maps of Figure-8

Figure 6: Visualization of induced maps of noisy Figure-8. Full size is
$1000$. Sample size is $20$.

Figure 7: Visualization of induced maps of noisy Figure-8. Full size is
$1000$. Sample size is $50$.

Figure 8: Visualization of induced maps of noisy Figure-8. Full size is
$1000$. Sample size is $100$.

Figure 9: Visualization of induced maps of noisy Figure-8. Full size is
$1000$. Sample size is $300$.

Figure 10: Visualization of induced maps of noisy Figure-8. Full size is
$1000$. Sample size is $500$.

Figure 11: Visualization of induced maps of noisy Figure-8. Full size is
$1000$. Sample size is $800$.

(a) Sample size is $20$. The threshold of Rips complex is
$0.25+\text{Hausdorff dist}*2$.

(b) Sample size is $50$. The threshold of Rips complex is
$0.25+\text{Hausdorff dist}*2$.

(c) Sample size is $100$. The threshold of Rips complex is
$0.25+\text{Hausdorff dist}*2$.

(d) Sample size is $300$. The threshold of Rips complex is $2$.

(e) Sample size is $500$. The threshold of Rips complex is $2$.

(f) Sample size is $800$. The threshold of Rips complex is $2$.

Figure 12: Visualization of induced maps of annulus from sub-samples to full
point cloud. Full size is $1000$.

Figure 13: Induced maps of noisy Annulus. Full point cloud size is $1000$.
Sample size is $20$.

Figure 14: Induced maps of noisy Annulus. Full point cloud size is $1000$.
Sample size is $50$.

Figure 15: Induced maps of noisy Annulus. Full point cloud size is $1000$.
Sample size is $100$.

Figure 16: Induced maps of noisy Annulus. Full point cloud size is $1000$.
Sample size is $300$.

Figure 17: Induced maps of noisy Annulus. Full point cloud size is $1000$.
Sample size is $500$.

Figure 18: Induced maps of noisy Annulus. Full point cloud size is $1000$.
Sample size is $800$.

Figure 19: Vietoris-Rips persistence diagrams of Figure-8. Sub-samples’ size
are $20$, $50$, $100$, $300$, $500$, and $800$ from top to bottom and left to
right respectively. We observe that there are two connected components
captured in each sample.

Figure 20: Vietoris-Rips persistence diagrams of Annulus. Sub-samples’ size
are $20$, $50$, $100$, $300$, $500$, and $800$ from left to right and top to
bottom respectively. We observe that there are two connected components
captured in each sample.