Search

The Gromov-Wasserstein (GW) distance is a powerful tool for comparing metric measure spaces which has found broad applications in data science and machine learning. Driven by the need to analyze datasets whose objects have increasingly complex structure (such as node and edge-attributed graphs), several variants of GW distance have been introduced in the recent literature. With a view toward establishing a general framework for the theory of GW-like distances, this paper considers a vast generalization of the notion of a metric measure space: for an arbitrary metric space $Z$, we define a $Z$-network to be a measure space endowed with a kernel valued in $Z$. We introduce a method for comparing $Z$-networks by defining a generalization of GW distance, which we refer to as $Z$-Gromov-Wasserstein ($Z$-GW) distance. This construction subsumes many previously known metrics and offers a unified approach to understanding their shared properties. The paper demonstrates that the $Z$-GW distance defines a metric on the space of $Z$-networks which retains desirable properties of $Z$, such as separability, completeness, and geodesicity. Many of these properties were unknown for existing variants of GW distance that fall under our framework. Our focus is on foundational theory, but our results also include computable lower bounds and approximations of the distance which will be useful for practical applications.

This writeup describes ongoing work on designing and testing a certain family of correspondences between compact metric spaces that we call \emph{embedding-projection correspondences} (EPCs). Of particular interest are EPCs between spheres of different dimension., Comment: working paper

In this paper, we bring a new perspective to persistent homology by incorporating key concepts from metric geometry. For a given compact subset $X$ of a Banach space $Y$, we study the topological features appearing in family $N_\bullet(X\subset Y)$ of nested of neighborhoods of $X$ in $Y$ and give several geometric bounds on their persistence (lifespans). First, we discuss the lifespans of these homology classes in terms of their filling radii in $Y$. By using this, we relate these lifespans to key invariants in metric geometry such as Urysohn width. Next, we bound these lifespans via $\ell^\infty$-principal components of the set $X$, which are also known as Kolmogorov widths. Furthermore, we introduce and study the notion of extinction time of a space $X$: the critical threshold after which there are no homological features alive in any degree. We also describe novel approaches on how to estimate \v{C}ech and Vietoris-Rips extinction times of a set $X$ by relating $X$ to its \"uber-contractible cores and to its tight span, respectively., Comment: 47 pages, 4 figures

We introduce a notion of distance between supervised learning problems, which we call the Risk distance. This optimal-transport-inspired distance facilitates stability results; one can quantify how seriously issues like sampling bias, noise, limited data, and approximations might change a given problem by bounding how much these modifications can move the problem under the Risk distance. With the distance established, we explore the geometry of the resulting space of supervised learning problems, providing explicit geodesics and proving that the set of classification problems is dense in a larger class of problems. We also provide two variants of the Risk distance: one that incorporates specified weights on a problem's predictors, and one that is more sensitive to the contours of a problem's risk landscape., Comment: 87 pages

We introduce Orthogonal M\"obius Inversion $\mathsf{OI}$, a concept analogous to M\"obius inversion on finite posets, which is applicable to order-preservings functions from a finite poset to the Grassmannian $\mathsf{Gr}(V)$ of an inner product space $V$. Orthogonal Inversion is a special case of the broader concept of Orthomodular Inversion, where the target space is any orthomodular lattice, which we also identify. We apply $\mathsf{OI}$ in order to construct a "non-negative" persistence diagram for multiparameter filtrations $\mathsf{F}$ of a finite simplicial complex $K$ indexed over an arbitrary finite poset $P$, by applying it to the birth-death spaces of $\mathsf{F}$. Analogously to $1$-parameter classical persistence diagrams, these multiparameter Grassmannian persistence diagrams offer straightforward interpretability. Specifically, to a segment $(b, d) \in \mathsf{Seg}(P)$, (1) the Grassmannian persistence diagram canonically assigns a vector subspace of $C_q^K$ consisting of cycles that are born at $b$ and become boundaries at $d$ and (2) this assignment is exhaustive at the homology level. In the case of 1-parameter filtrations, we also study a variant of $\mathsf{OI}$ that is applicable to persistent Laplacian kernels., Comment: Results in the previous version are generalized

Computing Persistent Homology for large point clouds remains a bottleneck for the wider adoption of persistent homology by the scientific community. We present an algorithm which can compute the degree-1 Vietoris-Rips Persistent Homology of point clouds in low dimensional Euclidean Space for larger point clouds., Comment: 54 pages, 19 figures, 5 tables

In this paper we consider a two-parameter family {dGWp,q}p,q of Gromov- Wasserstein distances between metric measure spaces. By exploiting a suitable interaction between specific values of the parameters p and q and the metric of the underlying spaces, we determine the exact value of the distance dGW4,2 between all pairs of unit spheres of different dimension endowed with their Euclidean distance and their uniform measure., Comment: 1. Added a Section 4, Section 5, and Appendix C; 2. Swapped Sections 2 and 3; 3. "Relagated Proofs" section (Section 4 in the old version) is now in appendix

Public health policy makers are faced with making crucial decisions rapidly during infectious disease outbreaks such as that caused by SARS-CoV-2. Ideally, rapidly deployed representative health surveys could provide needed data for such decisions. Under the constraints of a limited timeframe and resources, it may be infeasible to implement random based (probability) sampling that yields a population representative survey sample with high response rates. As an alternative, a volunteer (nonprobability) sample is often collected using outreach methods such as social media and web surveys. Compared to a probability sample, a nonprobability sample is subject to selection bias. In addition, when participants are followed longitudinally nonresponse often occurs at later follow up timepoints. As a result, estimates of cross-sectional parameters at later timepoints will be subject to selection bias and nonresponse bias. In this paper, we create kernel-weighted pseudoweights (KW) for the baseline survey participants and construct nonresponse-adjusted kw (kwNR) for respondents at each follow-visit to estimate the population mean at the follow-up visits. We develop Taylor Linearization variance estimation that accounts for variability due to estimating both pseudoweights and the nonresponse adjustments. Simulations are conducted to evaluate the proposed kwNR-weighted estimates. We investigate covariate effects on each of the following: baseline sample participation propensity, follow-up response propensity and the mean of the outcome. We apply the proposed kwNR-weighted methods to the SARS-Cov-2 antibody seropositivity longitudinal study, which begins with a baseline survey early in the pandemic, and collects data at six- and twelve-month post baseline follow-ups., Comment: 12 pages

We first introduce the notion of meta-rank for a 2-parameter persistence module, an invariant that captures the information behind images of morphisms between 1D slices of the module. We then define the meta-diagram of a 2-parameter persistence module to be the M\"{o}bius inversion of the meta-rank, resulting in a function that takes values from signed 1-parameter persistence modules. We show that the meta-rank and meta-diagram contain information equivalent to the rank invariant and the signed barcode. This equivalence leads to computational benefits, as we introduce an algorithm for computing the meta-rank and meta-diagram of a 2-parameter module $M$ indexed by a bifiltration of $n$ simplices in $O(n^3)$ time. This implies an improvement upon the existing algorithm for computing the signed barcode, which has $O(n^4)$ runtime. This also allows us to improve the existing upper bound on the number of rectangles in the rank decomposition of $M$ from $O(n^4)$ to $O(n^3)$. In addition, we define notions of erosion distance between meta-ranks and between meta-diagrams, and show that under these distances, meta-ranks and meta-diagrams are stable with respect to the interleaving distance. Lastly, the meta-diagram can be visualized in an intuitive fashion as a persistence diagram of diagrams, which generalizes the well-understood persistence diagram in the 1-parameter setting., Comment: 22 pages, 8 figures. Full version of the paper that is to appear in the Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023)

The graph Laplacian is a fundamental object in the analysis of and optimization on graphs. This operator can be extended to a simplicial complex $K$ and therefore offers a way to perform ``signal processing" on $p$-(co)chains of $K$. Recently, the concept of persistent Laplacian was proposed and studied for a pair of simplicial complexes $K\hookrightarrow L$ connected by an inclusion relation, further broadening the use of Laplace-based operators. In this paper, we expand the scope of the persistent Laplacian by generalizing it to a pair of simplicial complexes connected by a simplicial map $f: K \to L$. Such simplicial map setting arises frequently, e.g., when relating a coarsened simplicial representation with an original representation, or the case when the two simplicial complexes are spanned by different point sets i.e. cases in which it does not hold that $K\subset L$. However, the simplicial map setting is more challenging than the inclusion setting since the underlying algebraic structure is more complicated. We present a natural generalization of the persistent Laplacian to the simplicial setting. To shed insight on the structure behind it, as well as to develop an algorithm to compute it, we exploit the relationship between the persistent Laplacian and the Schur complement of a matrix. A critical step is to view the Schur complement as a functorial way of restricting a self-adjoint PSD operator to a given subspace. As a consequence, we prove that persistent Betti numbers of a simplicial map can be recovered by persistent Laplacians. We then propose an algorithm for finding the matrix representations of persistent Laplacians which in turn yields a new algorithm for computing persistent Betti numbers of a simplicial map. Finally, we study the persistent Laplacian on simplicial towers under simplicial maps and establish monotonicity results for their eigenvalues., Comment: This is the full version of a paper accepted to SoCG 2023. It contains 4 appendix sections to provide proofs, extra examples and other related results to the SoCG version

In this paper, we present a novel interpretation of the so-called Weisfeiler-Lehman (WL) distance, introduced by Chen et al. (2022), using concepts from stochastic processes. The WL distance aims at comparing graphs with node features, has the same discriminative power as the classic Weisfeiler-Lehman graph isomorphism test and has deep connections to the Gromov-Wasserstein distance. This new interpretation connects the WL distance to the literature on distances for stochastic processes, which also makes the interpretation of the distance more accessible and intuitive. We further explore the connections between the WL distance and certain Message Passing Neural Networks, and discuss the implications of the WL distance for understanding the Lipschitz property and the universal approximation results for these networks.

We generate anti-self-polar polytopes via a numerical implementation of the gradient flow induced by the diameter functional on the space of all finite subsets of the sphere, and prove related results on the critical points of the diameter functional as well as results about the combinatorics of such polytopes. We also discuss potential connections to Borsuk's conjecture., Comment: Updated funding information

We explore emerging relationships between the Gromov-Hausdorff distance, Borsuk-Ulam theorems, and Vietoris-Rips simplicial complexes. The Gromov-Hausdorff distance between two metric spaces $X$ and $Y$ can be lower bounded by the distortion of (possibly discontinuous) functions between them. The more these functions must distort the metrics, the larger the Gromov-Hausdorff distance must be. Topology has few tools to obstruct the existence of discontinuous functions. However, an arbitrary function $f\colon X\to Y$ induces a continuous map between their Vietoris-Rips simplicial complexes, where the allowable choices of scale parameters depend on how much the function $f$ distorts distances. We can then use equivariant topology to obstruct the existence of certain continuous maps between Vietoris-Rips complexes. With these ideas we bound how discontinuous an odd map between spheres $S^k\to S^n$ with $k>n$ must be, generalizing a result by Dubins and Schwarz (1981), which is the case $k=n+1$. As an application, we recover or improve upon all of the lower bounds from Lim, M\'emoli, and Smith (2022) on the Gromov-Hausdorff distances between spheres of different dimensions. We also provide new upper bounds on the Gromov-Hausdorff distance between spheres of adjacent dimensions.

Inspired by the Kantorovich formulation of optimal transport distance between probability measures on a metric space, Gromov-Wasserstein (GW) distances comprise a family of metrics on the space of isomorphism classes of metric measure spaces. In previous work, the authors introduced a variant of this construction which was inspired by the original Monge formulation of optimal transport; elements of the resulting family are referred to Gromov-Monge (GM) distances. These GM distances, and related ideas, have since become a subject of interest from both theoretical and applications-oriented perspectives. In this note, we establish several theoretical properties of GM distances, focusing on comparisons between GM and GW distances. In particular, we show that GM and GW distances are equal for non-atomic metric measure spaces. We also consider variants of GM distance, such as a Monge version of Sturm's $L_p$-transportion distance, and give precise comparisons to GW distance. Finally, we establish bi-H\"{o}lder equivalence between GM distance and an isometry-invariant Monge optimal transport distance between Euclidean metric measure spaces that has been utilized in shape and image analysis applications., Comment: V2: Accepted version. To appear: ESAIM: Control, Optimisation and Calculus of Variations. Some of these results appeared in an appendix to earlier versions of our previous paper arXiv:1810.09646, but were removed from the published version of that paper

One-dimensional persistent homology is arguably the most important and heavily used computational tool in topological data analysis. Additional information can be extracted from datasets by studying multi-dimensional persistence modules and by utilizing cohomological ideas, e.g.~the cohomological cup product. In this work, given a single parameter filtration, we investigate a certain 2-dimensional persistence module structure associated with persistent cohomology, where one parameter is the cup-length $\ell\geq0$ and the other is the filtration parameter. This new persistence structure, called the persistent cup module, is induced by the cohomological cup product and adapted to the persistence setting. Furthermore, we show that this persistence structure is stable. By fixing the cup-length parameter $\ell$, we obtain a 1-dimensional persistence module, called the persistent $\ell$-cup module, and again show it is stable in the interleaving distance sense, and study their associated generalized persistence diagrams. In addition, we consider a generalized notion of a persistent invariant, which extends both the rank invariant (also referred to as persistent Betti number), Puuska's rank invariant induced by epi-mono-preserving invariants of abelian categories, and the recently-defined persistent cup-length invariant, and we establish their stability. This generalized notion of persistent invariant also enables us to lift the Lyusternik-Schnirelmann (LS) category of topological spaces to a novel stable persistent invariant of filtrations, called the persistent LS-category invariant., Comment: Revised the improperly displayed figures and fixed some typos

For $n \geq 2$, the $n$-th curvature set of a metric space $X$ is the set consisting of all $n$-by-$n$ distance matrices of $n$ points sampled from $X$. Curvature sets can be regarded as a geometric analogue of configuration spaces. In this paper we carry out a geometric and topological study of the curvature sets of the unit circle $\mathbb{S}^1$ equipped with the geodesic metric. Via an inductive argument we compute the homology groups of all curvature sets of $\mathbb{S}^1$. We also construct an abstract simplicial complex, called the $n$-th State Complex, whose geometric realization is homeomorphic to the $n$-th Curvature Set of $\mathbb{S}^1$., Comment: Reworked Section 4 to work directly with cluster structures rather than using state matrices. As a bonus, we added a proof that the curvature sets of the circle are geometric simplicial complexes (Theorem 2), and we updated the appendix with the calculations of K_3 accordingly

We strengthen the usual stability theorem for Vietoris-Rips (VR) persistent homology of finite metric spaces by building upon constructions due to Usher and Zhang in the context of filtered chain complexes. The information present at the level of filtered chain complexes includes points with zero persistence which provide additional information to that present at homology level. The resulting invariant, called verbose barcode, which has a stronger discriminating power than the usual barcode, is proved to be stable under certain metrics that are sensitive to these ephemeral points. In some situations, we provide ways to compute such metrics between verbose barcodes. We also exhibit several examples of finite metric spaces with identical (standard) VR barcodes yet with different verbose VR barcodes thus confirming that these ephemeral points strengthen the standard VR barcode., Comment: This is a full version of a conference paper under the same name, that was accepted to SoCG 2023

In addition to inherent computational challenges, the absence of a canonical method for quantifying `persistence' in multi-parameter persistent homology remains a hurdle in its application. One of the best known quantifications of persistence for multi-parameter persistent homology is the rank invariant, which has recently evolved into the generalized rank invariant (GRI) by naturally extending its domain. This extension enables us to quantify persistence across a broader range of regions in the indexing poset compared to the rank invariant. However, the size of the domain of the GRI is generally formidable, making it desirable to restrict its domain to a more manageable subset for computational purposes. The foremost questions regarding such a restriction of the domain are: (1) How to restrict, if possible, the domain of the GRI without any loss of information? (2) When can we more compactly encode the GRI as a `persistence diagram'? (3) What is the trade-off between computational efficiency and the discriminating power of the GRI as the amount of the restriction on the domain varies? (4) What proxies exist for persistence diagrams in the multi-parameter setting that can be derived from the GRI? To address the first three questions, we generalize and axiomatize the classic fundamental lemma of persistent homology via the notion of M\"obius invertibility of the GRI which we propose. This extension also contextualizes known results regarding the (generalized) rank invariant within the classical theory of M\"obius inversion. We conduct a comprehensive comparison between M\"obius invertibility and other existing concepts related to the structural simplicity of persistence modules. We address the fourth question through the notion of motivic invariants. We demonstrate that many invariants from the literature can be both derived from the GRI and recast as motivic invariants., Comment: Exposition has improved throughout; 62 pages, 6 figures

The Weisfeiler-Lehman (WL) test is a classical procedure for graph isomorphism testing. The WL test has also been widely used both for designing graph kernels and for analyzing graph neural networks. In this paper, we propose the Weisfeiler-Lehman (WL) distance, a notion of distance between labeled measure Markov chains (LMMCs), of which labeled graphs are special cases. The WL distance is polynomial time computable and is also compatible with the WL test in the sense that the former is positive if and only if the WL test can distinguish the two involved graphs. The WL distance captures and compares subtle structures of the underlying LMMCs and, as a consequence of this, it is more discriminating than the distance between graphs used for defining the state-of-the-art Wasserstein Weisfeiler-Lehman graph kernel. Inspired by the structure of the WL distance we identify a neural network architecture on LMMCs which turns out to be universal w.r.t. continuous functions defined on the space of all LMMCs (which includes all graphs) endowed with the WL distance. Finally, the WL distance turns out to be stable w.r.t. a natural variant of the Gromov-Wasserstein (GW) distance for comparing metric Markov chains that we identify. Hence, the WL distance can also be construed as a polynomial time lower bound for the GW distance which is in general NP-hard to compute.

We generalize the classical Multidimensional Scaling procedure to the setting of general metric measure spaces. We develop a related spectral theory for the generalized cMDS operator, which provides a more natural and rigorous mathematical background for cMDS. Also, we show that the sum of all negative eigenvalues of the cMDS operator is a new invariant measuring non-flatness of a metric measure space. Furthermore, the cMDS output of several non-finite exemplar metric measures spaces, in particular the cMDS for spheres S^{d-1} and subsets of Euclidean space, are studied. Finally, we prove the stability of the generalized cMDS process with respect to the Gromov-Wasserstein distance., Comment: Major changes are the following: (1) Fixed the proof of Proposition 3.25 (2) We wrote a new Section 7 for further discussion

The smallest hyperconvex metric space containing a given metric space X is called the tight span of X. It is known that tight spans have many nice geometric and topological properties, and they are gradually becoming a target of research of both the metric geometry community and the topological/geometric data analysis community. In this paper, we study the tight span of n-spheres (with either geodesic metric or l infinity-metric).

The notion of generalized rank invariant in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. Naturally, computing these rank invariants efficiently is a prelude to computing any of these derived structures efficiently. We show that the generalized rank over a finite interval $I$ of a $\mathbb{Z}^2$-indexed persistence module $M$ is equal to the generalized rank of the zigzag module that is induced on a certain path in $I$ tracing mostly its boundary. Hence, we can compute the generalized rank over $I$ by computing the barcode of the zigzag module obtained by restricting the bifiltration inducing $M$ to that path. If the bifiltration and $I$ have at most $t$ simplices and points respectively, this computation takes $O(t^\omega)$ time where $\omega\in[2,2.373)$ is the exponent of matrix multiplication. Among others, we apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module $M$, determine whether $M$ is interval decomposable and, if so, compute all intervals supporting its summands., Comment: Full version of the paper in the Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022). Shortened the proof of Theorem 3.12 and added new sections 4.4 and 4.5; 21 pages, 4 figures

Ptolemy's inequality is a classic relationship between the distances among four points in Euclidean space. Another relationship between six distances is the 4-point condition, an inequality satisfied by the lengths of the six paths that join any four points of a metric (or weighted) tree. The 4-point condition also characterizes when a finite metric space can be embedded in such a tree. The curious observer might realize that these inequalities have similar forms: if one replaces addition and multiplication in Ptolemy's inequality with maximum and addition, respectively, one obtains the 4-point condition. We show that this similarity is more than a coincidence. We identify a family of Ptolemaic inequalities in CAT-spaces parametrized by a real number and show that a certain limit involving these inequalities, as the parameter goes to negative infinity, yields the 4-point condition, giving an elementary proof that the latter is the tropicalization of Ptolemy's inequality., Comment: Improved the introduction by adding the history of Ptolemy's inequality and related works, context for tropical geometry, and Gromov hyperbolicity. Added a dedicated section for definitions. Improved the bounds in Example 2.5 (used to be Example 3.3)

The Gromov-Hausdorff distance ($d_\mathrm{GH}$) provides a natural way of quantifying the dissimilarity between two given metric spaces. It is known that computing $d_\mathrm{GH}$ between two finite metric spaces is NP-hard, even in the case of finite ultrametric spaces which are highly structured metric spaces in the sense that they satisfy the so-called \emph{strong triangle inequality}. Ultrametric spaces naturally arise in many applications such as hierarchical clustering, phylogenetics, genomics, and even linguistics. By exploiting the special structures of ultrametric spaces, (1) we identify a one parameter family $\{d_\mathrm{GH}^{(p)}\}_{p\in[1,\infty]}$ of distances defined in a flavor similar to the Gromov-Hausdorff distance on the collection of finite ultrametric spaces, and in particular $d_\mathrm{GH}^{(1)} =d_\mathrm{GH}$. The extreme case when $p=\infty$, which we also denote by $u_\mathrm{GH}$, turns out to be an ultrametric on the collection of ultrametric spaces. Whereas for all $p\in[1,\infty)$, $d_\mathrm{GH}^{(p)}$ yields NP-hard problems, we prove that surprisingly $u_\mathrm{GH}$ can be computed in polynomial time. The proof is based on a structural theorem for $u_\mathrm{GH}$ established in this paper; (2) inspired by the structural theorem for $u_\mathrm{GH}$, and by carefully leveraging properties of ultrametric spaces, we also establish a structural theorem for $d_\mathrm{GH}$ when restricted to ultrametric spaces. This structural theorem allows us to identify special families of ultrametric spaces on which $d_\mathrm{GH}$ is computationally tractable. These families are determined by properties related to the doubling constant of metric space. Based on these families, we devise a fixed-parameter tractable (FPT) algorithm for computing the exact value of $d_\mathrm{GH}$ between ultrametric spaces. We believe ours is the first such algorithm to be identified.

A metric thickening of a given metric space $X$ is any metric space admitting an isometric embedding of $X$. Thickenings have found use in applications of topology to data analysis, where one may approximate the shape of a dataset via the persistent homology of an increasing sequence of spaces. We introduce two new families of metric thickenings, the $p$-Vietoris-Rips and $p$-\v{C}ech metric thickenings for all $1\le p\le \infty$, which include all measures on $X$ whose $p$-diameter or $p$-radius is bounded from above, equipped with an optimal transport metric. The $p$-diameter (resp. $p$-radius) of a measure is a certain $\ell_p$ relaxation of the usual notion of diameter (resp. radius) of a subset of a metric space. These families recover the previously studied Vietoris-Rips and \v{C}ech metric thickenings when $p=\infty$. As our main contribution, we prove a stability theorem for the persistent homology of $p$-Vietoris-Rips and $p$-\v{C}ech metric thickenings, which is novel even in the case $p=\infty$. In the specific case $p=2$, we prove a Hausmann-type theorem for thickenings of manifolds, and we derive the complete list of homotopy types of the $2$-Vietoris-Rips thickenings of the $n$-sphere as the scale increases.

We provide a complete taxonomic characterization of robust hierarchical clustering methods for directed networks following an axiomatic approach. We begin by introducing three practical properties associated with the notion of robustness in hierarchical clustering: linear scale preservation, stability, and excisiveness. Linear scale preservation enforces imperviousness to change in units of measure whereas stability ensures that a bounded perturbation in the input network entails a bounded perturbation in the clustering output. Excisiveness refers to the local consistency of the clustering outcome. Algorithmically, excisiveness implies that we can reduce computational complexity by only clustering a subset of our data while theoretically guaranteeing that the same hierarchical outcome would be observed when clustering the whole dataset. In parallel to these three properties, we introduce the concept of representability, a generative model for describing clustering methods through the specification of their action on a collection of networks. Our main result is to leverage this generative model to give a precise characterization of all robust -- i.e., excisive, linear scale preserving, and stable -- hierarchical clustering methods for directed networks. We also address the implementation of our methods and describe an application to real data., Comment: arXiv admin note: substantial text overlap with arXiv:1607.06339

Cohomological ideas have recently been injected into persistent homology and have for example been used for accelerating the calculation of persistence diagrams by the software Ripser. The cup product operation which is available at cohomology level gives rise to a graded ring structure that extends the usual vector space structure and is therefore able to extract and encode additional rich information. The maximum number of cocycles having non-zero cup product yields an invariant, the cup-length, which is useful for discriminating spaces. In this paper, we lift the cup-length into the persistent cup-length function for the purpose of capturing ring-theoretic information about the evolution of the cohomology (ring) structure across a filtration. We show that the persistent cup-length function can be computed from a family of representative cocycles and devise a polynomial time algorithm for its computation. We furthermore show that this invariant is stable under suitable interleaving-type distances., Comment: The full version of a paper accepted to SoCG 2022; contains 4 appendix sections to provide proofs, extra examples and other related results to the SoCG version. Compared to previous versions, the subsection about \ell-fold products of persistent cohomology is not included here. Readers interested in those results should refer to the older versions for now

The collection $\mathcal{M}$ of all isometry classes of compact metric spaces endowed with the Gromov-Hausdorff distance $d_\mathcal{GH}$ is known to be a geodesic space. However, there is no known structural characterization of geodesics in $\mathcal{M}$. In this paper we provide two such characterizations. We first prove that every Gromov-Hausdorff geodesic is in fact a geodesic in the Hausdorff hyperspace of some compact metric space, which we call a Hausdorff geodesic. Inspired by this characterization, we further elucidate a structural connection between Hausdorff geodesics and Wasserstein geodesics: every Hausdorff geodesic is equivalent to a so-called Hausdorff displacement interpolation. This equivalence allows us to establish that every Gromov-Hausdorff geodesic is dynamic, a notion which we develop in analogy with dynamic optimal couplings in the theory of optimal transport. Besides geodesics in $\mathcal{M}$, we also study geodesics on the collection $\mathcal{M}^w$ of isomorphism classes of compact metric measure spaces. Sturm constructed a family of Gromov-type distances on $\mathcal{M}^w$, which we denote $d_{\mathcal{GW},{p}}^\mathrm{S}$ (for $p\in[1,\infty)$), and proved that $(\mathcal{M}^w,d_{\mathcal{GW},{p}}^\mathrm{S})$ is also a geodesic space. We are interested in $d_{\mathcal{GW},{p}}^\mathrm{S}$ geodesics which are (essentially) Wasserstein geodesics. We prove the set of such geodesics is dense in the set of all $d_{\mathcal{GW},{p}}^\mathrm{S}$ geodesics and identify a rich class of such geodesics., Comment: minor edits

We provide general upper and lower bounds for the Gromov-Hausdorff distance $d_{\mathrm{GH}}(\mathbb{S}^m,\mathbb{S}^n)$ between spheres $\mathbb{S}^m$ and $\mathbb{S}^n$ (endowed with the round metric) for $0\leq m< n\leq \infty$. Some of these lower bounds are based on certain topological ideas related to the Borsuk-Ulam theorem. Via explicit constructions of (optimal) correspondences we prove that our lower bounds are tight in the cases of $d_{\mathrm{GH}}(\mathbb{S}^0,\mathbb{S}^n)$, $d_{\mathrm{GH}}(\mathbb{S}^m,\mathbb{S}^\infty)$, $d_{\mathrm{GH}}(\mathbb{S}^1,\mathbb{S}^2)$, $d_{\mathrm{GH}}(\mathbb{S}^1,\mathbb{S}^3)$ and $d_{\mathrm{GH}}(\mathbb{S}^2,\mathbb{S}^3)$. We also formulate a number of open questions., Comment: * We made some structural changes for better readability

We study a family of invariants of compact metric spaces that combines the Curvature Sets defined by Gromov in the 1980s with Vietoris-Rips Persistent Homology. For given integers $k\geq 0$ and $n\geq 1$ we consider the dimension $k$ Vietoris-Rips persistence diagrams of \emph{all} subsets of a given metric space with cardinality at most $n$. We call these invariants \emph{persistence sets} and denote them as $\mathbf{D}_{n,k}^\textrm{VR}$. We establish that (1) computing these invariants is often significantly more efficient than computing the usual Vietoris-Rips persistence diagrams, (2) these invariants have very good discriminating power and, in many cases, capture information that is imperceptible through standard Vietoris-Rips persistence diagrams, and (3) they enjoy stability properties. We precisely characterize some of them in the case of spheres and surfaces with constant curvature using a generalization of Ptolemy's inequality. We also identify a rich family of metric graphs for which $\mathbf{D}_{4,1}^\textrm{VR}$ fully recovers their homotopy type by studying split-metric decompositions. Along the way we prove some useful properties of Vietoris-Rips persistence diagrams using Mayer-Vietoris sequences. These yield a geometric algorithm for computing the Vietoris-Rips persistence diagram of a space $X$ with cardinality $2k+2$ with quadratic time complexity as opposed to the much higher cost incurred by the usual algebraic algorithms relying on matrix reduction., Comment: Added Example 4.15 (in Section 4.3) to show that persistence sets and persistent homology distinguish different spaces, and added more running time comparisons to Section 4.4

In this paper, we investigate compact ultrametric measure spaces which form a subset $\mathcal{U}^w$ of the collection of all metric measure spaces $\mathcal{M}^w$. Similar as for the ultrametric Gromov-Hausdorff distance on the collection of ultrametric spaces $\mathcal{U}$, we define ultrametric versions of two metrics on $\mathcal{U}^w$, namely of Sturm's distance of order $p$ and of the Gromov-Wasserstein distance of order $p$. We study the basic topological and geometric properties of these distances as well as their relation and derive for $p=\infty$ a polynomial time algorithm for their calculation. Further, several lower bounds for both distances are derived and some of our results are generalized to the case of finite ultra-dissimilarity spaces.

We present a thorough study of the theoretical properties and devise efficient algorithms for the \emph{persistent Laplacian}, an extension of the standard combinatorial Laplacian to the setting of pairs (or, in more generality, sequences) of simplicial complexes $K \hookrightarrow L$, which was independently introduced by Lieutier et al. and by Wang et al. In particular, in analogy with the non-persistent case, we first prove that the nullity of the $q$-th persistent Laplacian $\Delta_q^{K,L}$ equals the $q$-th persistent Betti number of the inclusion $(K \hookrightarrow L)$. We then present an initial algorithm for finding a matrix representation of $\Delta_q^{K,L}$, which itself helps interpret the persistent Laplacian. We exhibit a novel relationship between the persistent Laplacian and the notion of Schur complement of a matrix which has several important implications. In the graph case, it both uncovers a link with the notion of effective resistance and leads to a persistent version of the Cheeger inequality. This relationship also yields an additional, very simple algorithm for finding (a matrix representation of) the $q$-th persistent Laplacian which in turn leads to a novel and fundamentally different algorithm for computing the $q$-th persistent Betti number for a pair $(K,L)$ which can be significantly more efficient than standard algorithms. Finally, we study persistent Laplacians for simplicial filtrations and present novel stability results for their eigenvalues. Our work brings methods from spectral graph theory, circuit theory, and persistent homology together with a topological view of the combinatorial Laplacian on simplicial complexes., Comment: We realized that the origin of the persistent Laplacian can be dated back to a talk given by Lieutier in 2014 (https://project.inria.fr/gudhi/files/2014/10/Persistent-Harmonic-Forms.pdf). We changed several places in the paper to give credit to Lieutier et al