We study a family of invariants of compact metric spaces that combines the Curvature Sets defined by Gromov in the 1980 s with Vietoris–Rips Persistent Homology. For given integers
We study a generalization of the classical multidimensional scaling procedure (cMDS) which is applicable in the setting of metric measure spaces. Metric measure spaces can be seen as natural ‘continuous limits’ of finite data sets. Given a metric measure space ${\mathcal{X}} = (X,d_{X},\mu _{X})$, the generalized cMDS procedure involves studying an operator which may have infinite rank, a possibility which leads to studying its traceability. We establish that several continuous exemplar metric measure spaces such as spheres and tori (both with their respective geodesic metrics) induce traceable cMDS operators, a fact which allows us to obtain the complete characterization of the metrics induced by their resulting cMDS embeddings. To complement this, we also exhibit a metric measure space whose associated cMDS operator is not traceable. Finally, we establish the stability of the generalized cMDS method with respect to the Gromov–Wasserstein distance.
more » « less NSFPAR ID:
 10505784
 Publisher / Repository:
 Oxford University Press
 Date Published:
 Journal Name:
 Information and Inference: A Journal of the IMA
 Volume:
 13
 Issue:
 2
 ISSN:
 20498772
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract and$$k\ge 0$$ $k\ge 0$ we consider the dimension$$n\ge 1$$ $n\ge 1$k Vietoris–Rips persistence diagrams ofall subsets of a given metric space with cardinality at mostn . We call these invariantspersistence sets and denote them as . We first point out that this family encompasses the usual Vietoris–Rips diagrams. We then establish that (1) for certain range of values of the parameters$${\textbf{D}}_{n,k}^{\textrm{VR}}$$ ${D}_{n,k}^{\text{VR}}$n andk , computing these invariants is 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 analogous to those of the usual Vietoris–Rips persistence diagrams. 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 fully recovers their homotopy type by studying splitmetric 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$${\textbf{D}}_{4,1}^{\textrm{VR}}$$ ${D}_{4,1}^{\text{VR}}$X with cardinality with quadratic time complexity as opposed to the much higher cost incurred by the usual algebraic algorithms relying on matrix reduction.$$2k+2$$ $2k+2$ 
null (Ed.)Design variety metrics measure how much a design space is explored. We propose that a generalized class of entropy measures based on SharmaMittal entropy offers advantages over existing methods to measure design variety. We show that an exemplar metric from SharmaMittal entropy, which we call the Herfindahl–Hirschman Index for Design (HHID) has the following desirable advantages over existing metrics: (a) More Accuracy: It better aligns with human ratings compared to existing and commonly used treebased metrics for two new datasets; (b) Higher Sensitivity: It has higher sensitivity compared to existing methods when distinguishing between the variety of sets; (c) Allows Efficient Optimization: It is a submodular function, which enables us to optimize design variety using a polynomialtime greedy algorithm; and (d) Generalizes to Multiple Measures: The parametric nature of this metric allows us to fit the metric to better represent variety for new domains. The paper also contributes a procedure for comparing metrics used to measure variety via constructing ground truth datasets from pairwise comparisons. Overall, our results shed light on some qualities that good design variety metrics should possess and the nontrivial challenges associated with collecting the data needed to measure those qualities.more » « less

Abstract Applications in data science, shape analysis, and object classification frequently require comparison of probability distributions defined on different ambient spaces. To accomplish this, one requires a notion of distance on a given class of metric measure spaces—that is, compact metric spaces endowed with probability measures. Such distances are typically defined as comparisons between metric measure space invariants, such as distance distributions (also referred to as shape distributions, distance histograms, or shape contexts in the literature). Generally, distances defined in terms of distance distributions are actually pseudometrics, in that they may vanish when comparing nonisomorphic spaces. The goal of this paper is to set up a formal framework for assessing the discrimininative power of distance distributions, that is, the extent to which these pseudometrics fail to define proper metrics. We formulate several precise inverse problems in terms of these invariants and answer them in several categories of metric measure spaces, including the category of plane curves, where we give a counterexample to the curve histogram conjecture of Brinkman and Olver, the categories of embedded and Riemannian manifolds, where we obtain sphere rigidity results, and the category of metric graphs, where we obtain a local injectivity result along the lines of classical work of Boutin and Kemper on point cloud configurations. The inverse problems are further contextualized by the introduction of a variant of the Gromov–Wasserstein distance on the space of metric measure spaces, which is inspired by the original Monge formulation of optimal transport.

Abstract There are many ways of measuring and modeling taildependence in random vectors: from the general framework of multivariate regular variation and the flexible class of maxstable vectors down to simple and concise summary measures like the matrix of bivariate taildependence coefficients. This paper starts by providing a review of existing results from a unifying perspective, which highlights connections between extreme value theory and the theory of cuts and metrics. Our approach leads to some new findings in both areas with some applications to current topics in risk management.
We begin by using the framework of multivariate regular variation to show that extremal coefficients, or equivalently, the higherorder taildependence coefficients of a random vector can simply be understood in terms of random exceedance sets, which allows us to extend the notion of Bernoulli compatibility. In the special but important case of bivariate taildependence, we establish a correspondence between taildependence matrices and
 and$$L^1$$ ${L}^{1}$ embeddable finite metric spaces via the spectral distance, which is a metric on the space of jointly 1Fréchet random variables. Namely, the coefficients of the cutdecomposition of the spectral distance and of the TawnMolchanov maxstable model realizing the corresponding bivariate extremal dependence coincide. We show that line metrics are rigid and if the spectral distance corresponds to a line metric, the higher order taildependence is determined by the bivariate taildependence matrix.$$\ell _1$$ ${\ell}_{1}$Finally, the correspondence between
embeddable metric spaces and taildependence matrices allows us to revisit the realizability problem, i.e. checking whether a given matrix is a valid taildependence matrix. We confirm a conjecture of Shyamalkumar and Tao (2020) that this problem is NPcomplete.$$\ell _1$$ ${\ell}_{1}$ 
Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.more » « less