skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Probabilistic convergence and stability of random mapper graphs
Abstract We study the probabilistic convergence between the mapper graph and the Reeb graph of a topological space $${\mathbb {X}}$$ X equipped with a continuous function $$f: {\mathbb {X}}\rightarrow \mathbb {R}$$ f : X → R . We first give a categorification of the mapper graph and the Reeb graph by interpreting them in terms of cosheaves and stratified covers of the real line $$\mathbb {R}$$ R . We then introduce a variant of the classic mapper graph of Singh et al. (in: Eurographics symposium on point-based graphics, 2007), referred to as the enhanced mapper graph, and demonstrate that such a construction approximates the Reeb graph of $$({\mathbb {X}}, f)$$ ( X , f ) when it is applied to points randomly sampled from a probability density function concentrated on $$({\mathbb {X}}, f)$$ ( X , f ) . Our techniques are based on the interleaving distance of constructible cosheaves and topological estimation via kernel density estimates. Following Munch and Wang (In: 32nd international symposium on computational geometry, volume 51 of Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, Germany, pp 53:1–53:16, 2016), we first show that the mapper graph of $$({\mathbb {X}}, f)$$ ( X , f ) , a constructible $$\mathbb {R}$$ R -space (with a fixed open cover), approximates the Reeb graph of the same space. We then construct an isomorphism between the mapper of $$({\mathbb {X}},f)$$ ( X , f ) to the mapper of a super-level set of a probability density function concentrated on $$({\mathbb {X}}, f)$$ ( X , f ) . Finally, building on the approach of Bobrowski et al. (Bernoulli 23 (1):288–328, 2017b), we show that, with high probability, we can recover the mapper of the super-level set given a sufficiently large sample. Our work is the first to consider the mapper construction using the theory of cosheaves in a probabilistic setting. It is part of an ongoing effort to combine sheaf theory, probability, and statistics, to support topological data analysis with random data.  more » « less
Award ID(s):
1907591 1661375
PAR ID:
10295929
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Journal of Applied and Computational Topology
Volume:
5
Issue:
1
ISSN:
2367-1726
Page Range / eLocation ID:
99 to 140
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    Given a map f:X → M from a topological space X to a metric space M, a decorated Reeb space consists of the Reeb space, together with an attribution function whose values recover geometric information lost during the construction of the Reeb space. For example, when M = ℝ is the real line, the Reeb space is the well-known Reeb graph, and the attributions may consist of persistence diagrams summarizing the level set topology of f. In this paper, we introduce decorated Reeb spaces in various flavors and prove that our constructions are Gromov-Hausdorff stable. We also provide results on approximating decorated Reeb spaces from finite samples and leverage these to develop a computational framework for applying these constructions to point cloud data. 
    more » « less
  2. ; ; ; (, 40th International Symposium on Computational Geometry (SoCG 2024), Leibniz International Proceedings in Informatics (LIPIcs))
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    A Reeb graph is a graphical representation of a scalar function on a topological space that encodes the topology of the level sets. A Reeb space is a generalization of the Reeb graph to a multiparameter function. In this paper, we propose novel constructions of Reeb graphs and Reeb spaces that incorporate the use of a measure. Specifically, we introduce measure-theoretic Reeb graphs and Reeb spaces when the domain or the range is modeled as a metric measure space (i.e., a metric space equipped with a measure). Our main goal is to enhance the robustness of the Reeb graph and Reeb space in representing the topological features of a scalar field while accounting for the distribution of the measure. We first introduce a Reeb graph with local smoothing and prove its stability with respect to the interleaving distance. We then prove the stability of a Reeb graph of a metric measure space with respect to the measure, defined using the distance to a measure or the kernel distance to a measure, respectively. 
    more » « less
  3. ; ; (, International Mathematics Research Notices)
    Abstract We propose a new approach to deriving quantitative mean field approximations for any probability measure $$P$$ on $$\mathbb {R}^{n}$$ with density proportional to $$e^{f(x)}$$, for $$f$$ strongly concave. We bound the mean field approximation for the log partition function $$\log \int e^{f(x)}dx$$ in terms of $$\sum _{i \neq j}\mathbb {E}_{Q^{*}}|\partial _{ij}f|^{2}$$, for a semi-explicit probability measure $$Q^{*}$$ characterized as the unique mean field optimizer, or equivalently as the minimizer of the relative entropy $$H(\cdot \,|\,P)$$ over product measures. This notably does not involve metric-entropy or gradient-complexity concepts which are common in prior work on nonlinear large deviations. Three implications are discussed, in the contexts of continuous Gibbs measures on large graphs, high-dimensional Bayesian linear regression, and the construction of decentralized near-optimizers in high-dimensional stochastic control problems. Our arguments are based primarily on functional inequalities and the notion of displacement convexity from optimal transport. 
    more » « less
  4. ; ; ; (, International Mathematics Research Notices)
    null (Ed.)
    Abstract We consider the inequality $$f \geqslant f\star f$$ for real functions in $$L^1({\mathbb{R}}^d)$$ where $$f\star f$$ denotes the convolution of $$f$$ with itself. We show that all such functions $$f$$ are nonnegative, which is not the case for the same inequality in $L^p$ for any $$1 < p \leqslant 2$$, for which the convolution is defined. We also show that all solutions in $$L^1({\mathbb{R}}^d)$$ satisfy $$\int _{{\mathbb{R}}^{\textrm{d}}}f(x)\ \textrm{d}x \leqslant \tfrac 12$$. Moreover, if $$\int _{{\mathbb{R}}^{\textrm{d}}}f(x)\ \textrm{d}x = \tfrac 12$$, then $$f$$ must decay fairly slowly: $$\int _{{\mathbb{R}}^{\textrm{d}}}|x| f(x)\ \textrm{d}x = \infty $$, and this is sharp since for all $r< 1$, there are solutions with $$\int _{{\mathbb{R}}^{\textrm{d}}}f(x)\ \textrm{d}x = \tfrac 12$$ and $$\int _{{\mathbb{R}}^{\textrm{d}}}|x|^r f(x)\ \textrm{d}x <\infty $$. However, if $$\int _{{\mathbb{R}}^{\textrm{d}}}f(x)\ \textrm{d}x =: a < \tfrac 12$$, the decay at infinity can be much more rapid: we show that for all $$a<\tfrac 12$$, there are solutions such that for some $$\varepsilon>0$$, $$\int _{{\mathbb{R}}^{\textrm{d}}}e^{\varepsilon |x|}f(x)\ \textrm{d}x < \infty $$. 
    more » « less
  5. ; ; (, Computing in Geometry and Topology)
    Reeb graphs are widely used in a range of fields for the purposes of analyzing and comparing complex spaces via a simpler combinatorial object. Further, they are closely related to extended persistence diagrams, which largely but not completely encode the information of the Reeb graph. In this paper, we investigate the effect on the persistence diagram of a particular continuous operation on Reeb graphs; namely the (truncated) smoothing operation. This construction arises in the context of the Reeb graph interleaving distance, but separately from that viewpoint provides a simplification of the Reeb graph which continuously shrinks small loops. We then use this characterization to initiate the study of inverse problems for Reeb graphs using smoothing by showing which paths in persistence diagram space (commonly known as vineyards) can be realized by a path in the space of Reeb graphs via these simple operations. This allows us to solve the inverse problem on a certain family of piecewise linear vineyards when fixing an initial Reeb graph. While this particular application is limited in scope, it suggests future directions to more broadly study the inverse problem on Reeb graphs. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email