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.
 Award ID(s):
 1760485
 NSFPAR ID:
 10465354
 Date Published:
 Journal Name:
 Algorithms
 Volume:
 16
 Issue:
 3
 ISSN:
 19994893
 Page Range / eLocation ID:
 131
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
Oliva, Gabriele (Ed.)We define a new family of similarity and distance measures on graphs, and explore their theoretical properties in comparison to conventional distance metrics. These measures are defined by the solution(s) to an optimization problem which attempts find a map minimizing the discrepancy between two graph Laplacian exponential matrices, under normpreserving and sparsity constraints. Variants of the distance metric are introduced to consider such optimized maps under sparsity constraints as well as fixed timescaling between the two Laplacians. The objective function of this optimization is multimodal and has discontinuous slope, and is hence difficult for univariate optimizers to solve. We demonstrate a novel procedure for efficiently calculating these optima for two of our distance measure variants. We present numerical experiments demonstrating that (a) upper bounds of our distance metrics can be used to distinguish between lineages of related graphs; (b) our procedure is faster at finding the required optima, by as much as a factor of 10 3 ; and (c) the upper bounds satisfy the triangle inequality exactly under some assumptions and approximately under others. We also derive an upper bound for the distance between two graph products, in terms of the distance between the two pairs of factors. Additionally, we present several possible applications, including the construction of infinite “graph limits” by means of Cauchy sequences of graphs related to one another by our distance measure.more » « less

null (Ed.)Selfassembly of proteins on lipid membranes underlies many important processes in cell biology, such as, exo and endocytosis, assembly of viruses, etc. An attractive force that can cause selfassembly is mediated by membrane thickness interactions between proteins. The free energy profile associated with this attractive force is a result of the overlap of thickness deformation fields around the proteins which can be calculated from the solution of a boundary value problem. Yet, the time scales over which two inclusions coalesce has not been explored, even though the evolution of particle concentrations on membranes has been modeled using phasefield approaches. In this paper we compute this time scale as a function of the initial distance between two inclusions by viewing their coalescence as a first passage time problem. The mean first passage time is computed using Langevin dynamics and a partial differential equation, and both methods are found to be in excellent agreement. Inclusions of three different shapes are studied and it is found that for two inclusions separated by about hundred nanometers the time to coalescence is hundreds of milliseconds irrespective of shape. An efficient computation of the interaction energy of inclusions is central to our work. We compute it using a finite difference technique and show that our results are in excellent agreement with those from a previously proposed semianalytical method based on Fourier–Bessel series. The computational strategies described in this paper could potentially lead to efficient methods to explore the kinetics of selfassembly of proteins on lipid membranes.more » « less

For unweighted graphs, finding isometric embeddings of a graph G is closely related to decompositions of G into Cartesian products of smaller graphs. When G is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of G. When G is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of G. Prior work has shown that an unweighted graph’s pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph G, where G satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, ’85] and Feder [Feder, ’92] for pseudofactorization and factorization of unweighted graphs. We show that any nvertex, medge graph with positive integer edge weights can be factored in O(m2) time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of O(m2+n2 log log n) time. We also show that a pseudofactorization for such a graph can be computed in O(mn) time, plus the time to solve APSP, resulting in an O(mn + n2 log log n) running time.more » « less

Abstract An important hypothesis in animal cell biology is that an animal’s acute exercise regimen affects some subcellular structures, for example mitochondrial morphology, in its muscle tissue. This paper investigates that hypothesis using a nonparametric metricbased energy test for comparing mitochondrial populations. It explores two shape spaces—the elastic shape space and Kendall shape space—and five corresponding shape metrics on these spaces. The results overwhelmingly point to the statistical significance of the effect of an acute exercise regimen on the shape of SStype mitochondria. Although past studies based on specific morphological features derived from mitochondria failed to detect this significance. In this analysis, a potentially significant factor is cell membership and a ksample generalization of the energy test—the DISCO test shows that the cell effect is indeed significant. The energy test cannot be applied directly due to the hierarchical structure of the distance matrix. We propose a compression method to remove the significant cell effect while testing for the exercise effect. With this compression, only the elastic scaled metric shows statistical significance of the exercise factor in this more complicated scenario. This result is because the elasticscaled metric is more sensitive to subtle changes in mitochondrial shapes caused by acute exercise.