Glossary

Matrices

Sparse matrix

A sparse matrix is a matrix \(S\) where each entry \(S_{ij}\) has either an explicit numeric value, or a value of None.

By common convention, we call \(S_{ij}\)

structurally zero if it is None, and
structurally nonzero if it has an explicit numeric value – even if that value is zero.

Contrast with other definitions

The term sparse matrix has several other common uses; it often refers to any matrix with a large number of zeros.
Many authors treat None as zero entries which are not stored in computer memory. This assumption works poorly in the setting of topological data analysis. For example, if \(S\) represents the adjacency matrix of a graph, then \(S_{ij} = None\) typically indicate that there is no edge between vertices \(i\) and \(j\), while \(S_{ij} = 0\) typically indicates that there is an edge between \(i\) and \(j\) with weight zero.

Scipy sparse CSR matrices

A Scipy sparse CSR matrix is a sparse matrix represented in the Compressed Sparse Row (CSR) format. This format is efficient for arithmetic operations, matrix-vector products, and slicing. It is commonly used in Python for representing large sparse matrices, especially in scientific computing and data analysis.

Caution

Unsorted indices

Scipy sparse CSR matrices do not require that the column indices of the nonzero entries be sorted (within each row). Moreover, there is no built-in method to check that this sorting condition is satisfied. Scipy CSR matrices do have a property flag called has_sorted_indices, but this flag does not automatically update if the user manually modifies matrix.indices, which is sometimes necessary in topological data analysis.

Matrix oracle

A matrix oracle is an object that provides access to the entries of a matrix \(D\) without storing the entire matrix in memory. It is typically used for large matrices where storing the entire matrix would be impractical. An oracle may provide methods to access individual entries, rows, or columns of the matrix as needed.

Example In OAT, the oat_python.core.vietoris_rips.VietorisRipsMatrixOracle class is an example of a matrix oracle. It provides access to the entries of a Vietoris-Rips boundary matrix without storing the entire matrix in memory.

Umatch decomposition

A Umatch decomposition of a matrix \(D\) is a tuple of matrices \((T, M, D, S)\) such that

\(TM = DS\). This implicitly requres \(S\) and \(M\) to have the same number of columns as \(D\), and \(T\) and \(M\) to have the same number of rows as \(D\).
\(S\) and \(T\) are square upper triangular matrices with ones on the diagonal
\(M\) is a generalized matching matrix, meaning that \(M\) has at most one nonzero entry per row and column

Differential Umatch decomposition

A differential Umatch decomposition for a simplicial complex \(K\) is a Umatch decomposition for the differential matrix \(D\) of \(K\). We require this decomposition to have the form \((J, M, D, J)\), thus \(JM = DJ\). We also require J to be homogeneous with respect to dimension, meaning that each column of \(J\) represents a linear combination of simplices of the same dimension.

Graphs and simplicial complexes

Simple graph

An undirected graph \(G = (V,E)\) where each edge is an unordered pair of distinct vertices, i.e. \(E \subseteq \{\{i,j\} \mid i,j \in V, i \neq j\}\).

Every simple graph is equivalent to an abstract simplicial complex \(K\) where

The vertices of \(K\) are the vertices of \(G\)
\(K\) contains a simplex \(\{v\}\) for each vertex \(v \in V\) and a simplex \(\{u,v\}\) for each edge \(\{u,v\} \in E\).

Abstract simplicial complex

A set \(K\) of finite sets (called simplices) such that if \(\sigma \in K\) and \(\tau \subseteq \sigma\), then \(\tau \in K\). In other words, every subset of a simplex in \(K\) is also a simplex in \(K\). - The elements of \(K\) are called the simplices of the complex. - A simplex containing \(k+1\) vertices is called a k-simplex.

Vietoris Rips complex

Definition Let \(G = (V,E)\) be an unweighted simple graph. The Vietoris Rips complex of \(G\) is the abstract simplicial complex whose vertices are the vertices of \(G\), and whose simplices are the subsets of \(V\) that induce a complete subgraph in \(G\). In other words, a subset \(\sigma \subseteq V\) is a simplex in the Vietoris Rips complex if and only if every pair of vertices in \(\sigma\) is connected by an edge in \(G\).

Filtrations and filter functions Every filter function \(w: E \cup V \to \mathbb{R}\) defined on the vertices and edges of \(G\) extends naturally to a filter function on the simplices of the associated Vietoris Rips complex \(K\). Specifically, for each simplex \(\sigma \in K\), the filtration value is defined as the maximum filtration value of its vertices and edges:

\[w(\sigma) = \max \left ( \max_{v \in \sigma} w(v), \max_{e \in E(\sigma)} w(e) \right )\]

where \(E(\sigma)\) is the set of edges contained in \(\sigma\).

Point clouds and metric spaces Given a metric space or a point cloud, we can define the filtered Vietoris Rips complex as the filtered Vietoris Rips complex of the (filtered) complete graph \(G\) where the vertices are the points in the point cloud, the filtration value of each vertex is zero, and the filtration value of each edge is the distance between the two points it connects.

(Sparse) dissimilarity matrices The filtered Vietoris Rips complex of a (sparse) dissimilarity matrix \(D\) is the filtered Vietoris Rips complex of the associated filtered simple graph.

Differential matrix

The differential matrix of a simplicial complex \(K\) is a matrix \(D\) which has a row and column for each simplex in \(K\), and where \(\partial \sigma = \sum_{\tau \in K} D_{\tau, \sigma} \tau\) for each simplex \(\sigma \in K\). This matrix is also called the boundary matrix of \(K\).

Filtrations

Filter function

A filter function on an abstract simplicial complex \(K\) is a function \(w: K \to \mathbb{R}\) that assigns a real number to each simplex in \(K\). We require that the function be monotone, meaning that if \(\sigma \subseteq \tau\) are simplices in \(K\), then

\[w(\sigma) \leq w(\tau)\]

In other words, the weight of a simplex cannot exceed the weight of any of its supersimplices.

Filtrations The notion of a filter function is interchangeable with that of a filtration: the sublevel sets of a filter function \(w: K \to \mathbb{R}\) define a filtration of \(K\), and conversely a filtration on \(K\) defines a filter function by assigning to each simplex the minimum filtration parameter at which it appears.

Simple graphs A filter function on a simple graph \(G = (V,E)\) is defined as a filter function \(w\) on the associated abstract simplicial complex, \(K\). This can be thought of, equivalently, as a function \(w': V \cup E \to \mathbb{R}\) that assigns a real number to each vertex and edge of the graph, where \(w'(v) = w(\{v\})\) for each vertex \(v\).

Filtration

A filtration of an abstract simplicial complex \(K\) is a family of simplicial complexes \((K_t)_{t \in \mathbb{R}}\) such that for each \(t \in \mathbb{R}\), \(K_t\) is a subcomplex of \(K\) and if \(s \le t\), then \(K_s \subseteq K_t\). In other words, the filtration is a nested sequence of subcomplexes indexed by the real numbers.

The notion of a filtration is interchangeable with that of a filter function: the sublevel sets of a filter function \(w: K \to \mathbb{R}\) define a filtration of \(K\), and conversely a filtration on \(K\) defines a filter function by assigning to each simplex the minimum filtration parameter at which it appears.

Filtered simple graph

This term refers to a simple graph \(G = (V,E)\) equipped with a filter function \(w: V \cup E \to \mathbb{R}\). The vertices of the graph are assigned weights, and the edges are also assigned weights.

Dissimilarity

Dissimilarity matrix

This term refers to any (dense, as compared with sparse) symmetric \(n\times n\) matrix \(D\) where diagonal entries are the minima of their respective rows; that is, \(D_{ii} = \min_{j} D_{ij}\) for all \(i\).

Interpretation This type of matrix is often used to represent dissimilarities between points in a point cloud, but it can also refer to matrices that represent other measures of dissimilarity which don’t satisfy the conditions of a metric space, e.g. subjective human judgements.

The associated filtered graph is the complete graph \(G = (V,E)\) on vertex set \(1, \ldots, n\), equiped with the filter function \(w: V \cup E \to \mathbb{R}\) such that \(w(i) = D_{ii}\) for all \(i\), and \(w(i,j) = D_{ij}\) for all \(i \neq j\). In other words, the weight of each vertex is its diagonal entry in the matrix, and the weight of each edge is the corresponding off-diagonal entry. This weight function is an example of a filter function, because each vertex receives a value no greater than its incident edges.

Sparse dissimilarity matrix

This term refers to the sparse filtered adjacency matrix \(D\) of filtered simple graph. It can be characterized in several equivalent ways:

Definition 1 An \(n \times n\) sparse matrix \(D\) meets this condition if for all \(i \neq j\) in \(\{1, \ldots, n\}\),

\(D_{ij} = D_{ji}\)
In particular \(D_{ij}\) structurally nonzero if and only if \(D_{ji}\) is structurally nonzero.
If row i contains one or more structural nonzero entries, then \(D_{ii}\) is structurally nonzero, and \(D_{ii} = \min_j D_{ij}\) where \(j\) runs over all indices such that \(D_{ij}\) is structurally nonzero.

Definition 2 An \(n \times n\) sparse matrix \(D\) meets this condition if there is a simple graph \(G = (V,E)\) with vertex set \(V \subseteq \{1, \ldots, n\}\) and edge set \(E \subseteq V \times V\), equipped with a filter function \(w: V \cup E \to \mathbb{R}\) such that for all \(i \in \{1, \ldots, n\}\),

\[\begin{split}D_{ii} &= \begin{cases} w(\{i\}) & i \in V \\ \mathrm{None} & else \end{cases}\end{split}\]

and for all \(i \neq j\) in \(\{1, \ldots, n\}\),

\[\begin{split}D_{ij} &= \begin{cases} w(\{i,j\}) & \{i, j\} \in E \\ \mathrm{None} & else \end{cases}\end{split}\]

We call \(G\) the filtered simple graph associated to \(D\).

Associated filtered graph The associated filtered simple graph is the graph \(G = (V,E)\) where

The vertex set \(V\) is the set of indices \(i\) such that \(D_{ii}\) is structurally nonzero.
The edge set \(E\) is the set of pairs \((i,j)\) such that \(D_{ij}\) is structurally nonzero, and the weight function \(w: V \cup E \to \mathbb{R}\) is defined by
- \(w(i) = D_{ii}\) for all \(i \in V\)
- \(w(i,j) = D_{ij}\) for all \(i \neq j\) in \(V\).

Dissimilarity space

We use the term dissimilarity space interchangeablly with the term filtered simple graph. In many cases, this graph is repersented by a sparse dissimilarity matrix.

In this context we often talk about the dissimilarity between two vertices \(i\) and \(j\), meaning the filtration value (or weight) of the edge \(w(\{i,j\})\).

Enclosing radius

The enclosing radius of an \(n \times n\) dissimilarity matrix \(D_{ij}\) is the minimum of the row-wise maxima of \(D_{ij}\). In symbols, it is defined as

\[r_{\mathrm{enc}}(D) = \min_{i} \left( \max_{j} D_{ij} \right)\]

Empty matrices If \(n = 0\), then we define \(r_{\mathrm{enc}}(D) = +\infty\). This is consistent with the convention that the minimum of an empty set is \(+\infty\).

Only for dense matrices The enclosing radius is undefined for sparse dissimilarity matrices, although it can be used to sparsify a dense dissimilarity matrix. See below for details.

Interpretation for point clouds and metric spaces: The enclosing radius can be interpreted in the context of point clouds and their dissimilarity matrices. If we have a point cloud \(X = \{x_1, x_2, \ldots, x_n\}\) with a distance function \(d(\cdot, \cdot)\), then the enclosing radius captures the smallest maximum distance from any point to all other points in the cloud.

Significance in topological data analysis: The enclosing radius marks an upper bound on the filtration values of a filtered Vietoris Rips complex that have interesting homology:

Theorem

Suppose that \(n \ge 0\), and let \((K_t)_{t \in \mathbb{R}}\) be the filtered Vietoris Rips complex of \(D\). Then the homology of \(K_t\) is trivial (formally, isomorphic to the homology of a single point) for all \(t \geq r_{\mathrm{enc}}(D)\).

Consequently, if \(H\) is the sparse dissimilarity matrix obtained from \(D\) by deleting entry \(D_{ij}\) for all \(i \neq j\) such that \(D_{ij} > r_{\mathrm{enc}}(D)\), then the filtered Vietoris Rips complexes of \(D\) and \(H\) have isomorphic persistent homology.

This has significant practical implications, because the time and memory cost of computing persistent homology of the filtered Vietoris Rips complex of \(H\) is often orders of magnitude smaller than that of \(D\).

Caution

Numerical error

Distance computations in Python are subject to numerical error. Therefore, if you use the enclosing radius to sparsify a dissimilarity matrix for a Vietoris-Rips persistent homology calculation, it’s important to add a small buffer, e.g. enclosing_radius + 0.00000001, to avoid over-sparsification.

Details

Numerical error appears in many places in Python; for example,

euclidean_distance_one_sided( pointa, pointb ) sometimes returns a value slightly different from euclidean_distance_one_sided( pointb, pointa ), even though the only difference between the two calls is the order of the arguments.
sklearn.neighbors.radius_neighbors_graph often produces asymmetric matrices
sklearn.metrics.pairwise_distances often produces asymmetric matrices

Moreover, it’s common to calculate the same quantity multiply times in different ways for a single workflow, resulting in slightly different error values. Suppose, for example, that we want to compute the Vietoris Rips persistent homology of a point cloud that has many points. In this case, we often want to avoid computing a dense distance matrix, because it is expensive to compute and store. Instead, we want to directly compute a sparse dissimilarity matrix where all values greater than the enclosing radius are removed. To do this, we can

First calculate the enclosing radius of the distance matrix by calling oat_python.dissimilarity.enclosing_radius_for_cloud(cloud). This function only holds one row of the distance matrix in memory at a time, so it is much more memory-efficient than computing the entire distance matrix.
Then calculate the sparse dissimilarity matrix by calling oat_python.dissimilarity.sparse_dissimilarity_matrix_for_cloud(cloud, enclosing_radius + 0.00000001).

The reason for adding 0.00000001 is that distances computed by the function oat_python.dissimilarity.enclosing_radius_for_cloud may vary slightly from those computed by oat_python.dissimilarity.sparse_dissimilarity_matrix_for_cloud. Therefore, if we are unlucky, then calling oat_python.dissimilarity.sparse_dissimilarity_matrix_for_cloud(cloud, enclosing_radius) may delete some entries that should not be deleted.

In summary

Adding a buffer value of 0.00000001` (or some other small value) to the enclosing radius ensures that we do not delete important entries.
This may result in a slightly larger sparse dissimilarity matrix than necessary, but the persistent homology calculation on this larger matrix will be correct, and the additional time and memory needed to compute persistent homology will be negligible.
No buffer is needed if you know that all distances used for the enclosing radius and the sparse dissimilarity matrix are computed in exactly the same way. For example, oat_python.dissimilarity.enclosing_radius_for_cloud_slow and oat_python.dissimilarity.sparse_dissimilarity_matrix_for_cloud_slow are specifically engineered to work together, with no need for a buffer.