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.


Title: Bounding the interleaving distance for mapper graphs with a loss function
Abstract Data consisting of a graph with a function mapping into$${\mathbb {R}}^d$$ R d arise in many data applications, encompassing structures such as Reeb graphs, geometric graphs, and knot embeddings. As such, the ability to compare and cluster such objects is required in a data analysis pipeline, leading to a need for distances between them. In this work, we study the interleaving distance on discretization of these objects, called mapper graphs when$$d=1$$ d = 1 , where functor representations of the data can be compared by finding pairs of natural transformations between them. However, in many cases, computation of the interleaving distance is NP-hard. For this reason, we take inspiration from recent work by Robinson to find quality measures for families of maps that do not rise to the level of a natural transformation, called assignments. We then endow the functor images with the extra structure of a metric space and define a loss function which measures how far an assignment is from making the required diagrams of an interleaving commute. Finally we show that the computation of the loss function is polynomial with a given assignment. We believe this idea is both powerful and translatable, with the potential to provide approximations and bounds on interleavings in a broad array of contexts.  more » « less
Award ID(s):
2145499 2301361
PAR ID:
10617509
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Journal of Applied and Computational Topology
Volume:
9
Issue:
3
ISSN:
2367-1726
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.arXiv:2010.09793) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators$$L_{\beta ,\gamma } =- {\text {div}}D^{d+1+\gamma -n} \nabla $$ L β , γ = - div D d + 1 + γ - n associated to a domain$$\Omega \subset {\mathbb {R}}^n$$ Ω R n with a uniformly rectifiable boundary$$\Gamma $$ Γ of dimension$$d < n-1$$ d < n - 1 , the now usual distance to the boundary$$D = D_\beta $$ D = D β given by$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$ D β ( X ) - β = Γ | X - y | - d - β d σ ( y ) for$$X \in \Omega $$ X Ω , where$$\beta >0$$ β > 0 and$$\gamma \in (-1,1)$$ γ ( - 1 , 1 ) . In this paper we show that the Green functionGfor$$L_{\beta ,\gamma }$$ L β , γ , with pole at infinity, is well approximated by multiples of$$D^{1-\gamma }$$ D 1 - γ , in the sense that the function$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^2$$ | D ( ln ( G D 1 - γ ) ) | 2 satisfies a Carleson measure estimate on$$\Omega $$ Ω . We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear). 
    more » « less
  2. Abstract In this paper, we present counterexamples to maximal$$L^p$$ L p -regularity for a parabolic PDE. The example is a second-order operator in divergence form with space and time-dependent coefficients. It is well-known from Lions’ theory that such operators admit maximal$$L^2$$ L 2 -regularity on$$H^{-1}$$ H - 1 under a coercivity condition on the coefficients, and without any regularity conditions in time and space. We show that in general one cannot expect maximal$$L^p$$ L p -regularity on$$H^{-1}(\mathbb {R}^d)$$ H - 1 ( R d ) or$$L^2$$ L 2 -regularity on$$L^2(\mathbb {R}^d)$$ L 2 ( R d )
    more » « less
  3. Abstract Consider two half-spaces$$H_1^+$$ H 1 + and$$H_2^+$$ H 2 + in$${\mathbb {R}}^{d+1}$$ R d + 1 whose bounding hyperplanes$$H_1$$ H 1 and$$H_2$$ H 2 are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$ S 2 , + d : = S d H 1 + H 2 + is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$ S d , which contains a great subsphere of dimension$$d-2$$ d - 2 and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$ S 2 , + d and consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$ log n . A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$ S 2 , + d . The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere. 
    more » « less
  4. Abstract In this paper we prove a higher dimensional analogue of Carleson’s$$\varepsilon ^{2}$$ ε 2 conjecture. Given two arbitrary disjoint Borel sets$$\Omega ^{+},\Omega ^{-}\subset \mathbb{R}^{n+1}$$ Ω + , Ω R n + 1 , and$$x\in \mathbb{R}^{n+1}$$ x R n + 1 ,$$r>0$$ r > 0 , we denote$$ \varepsilon _{n}(x,r) := \frac{1}{r^{n}}\, \inf _{H^{+}} \mathcal{H}^{n} \left ( ((\partial B(x,r)\cap H^{+}) \setminus \Omega ^{+}) \cup (( \partial B(x,r)\cap H^{-}) \setminus \Omega ^{-})\right ), $$ ε n ( x , r ) : = 1 r n inf H + H n ( ( ( B ( x , r ) H + ) Ω + ) ( ( B ( x , r ) H ) Ω ) ) , where the infimum is taken over all open affine half-spaces$$H^{+}$$ H + such that$$x \in \partial H^{+}$$ x H + and we define$$H^{-}= \mathbb{R}^{n+1} \setminus \overline{H^{+}}$$ H = R n + 1 H + . Our first main result asserts that the set of points$$x\in \mathbb{R}^{n+1}$$ x R n + 1 where$$ \int _{0}^{1} \varepsilon _{n}(x,r)^{2} \, \frac{dr}{r}< \infty $$ 0 1 ε n ( x , r ) 2 d r r < is$$n$$ n -rectifiable. For our second main result we assume that$$\Omega ^{+}$$ Ω + ,$$\Omega ^{-}$$ Ω are open and that$$\Omega ^{+}\cup \Omega ^{-}$$ Ω + Ω satisfies the capacity density condition. For each$$x \in \partial \Omega ^{+} \cup \partial \Omega ^{-}$$ x Ω + Ω and$$r>0$$ r > 0 , we denote by$$\alpha ^{\pm }(x,r)$$ α ± ( x , r ) the characteristic constant of the (spherical) open sets$$\Omega ^{\pm }\cap \partial B(x,r)$$ Ω ± B ( x , r ) . We show that, up to a set of$$\mathcal{H}^{n}$$ H n measure zero,$$x$$ x is a tangent point for both$$\partial \Omega ^{+}$$ Ω + and$$\partial \Omega ^{-}$$ Ω if and only if$$ \int _{0}^{1} \min (1,\alpha ^{+}(x,r) + \alpha ^{-}(x,r) -2) \frac{dr}{r} < \infty . $$ 0 1 min ( 1 , α + ( x , r ) + α ( x , r ) 2 ) d r r < . The first result is new even in the plane and the second one improves and extends to higher dimensions the$$\varepsilon ^{2}$$ ε 2 conjecture of Carleson. 
    more » « less
  5. Abstract A model based on a$$U(1)_{T^3_R}$$ U ( 1 ) T R 3 extension of the Standard Model can address the mass hierarchy between generations of fermions, explain thermal dark matter abundance, and the muon$$g - 2$$ g - 2 ,$$R_{(D)}$$ R ( D ) , and$$R_{(D^*)}$$ R ( D ) anomalies. The model contains a light scalar boson$$\phi '$$ ϕ and a heavy vector-like quark$$\chi _\textrm{u}$$ χ u that can be probed at CERN’s large hadron collider (LHC). We perform a phenomenology study on the production of$$\phi '$$ ϕ and$${\chi }_u$$ χ u particles from proton–proton$$(\textrm{pp})$$ ( pp ) collisions at the LHC at$$\sqrt{s}=13.6$$ s = 13.6 TeV, primarily through$$g{-g}$$ g - g and$$t{-\chi _\textrm{u}}$$ t - χ u fusion. We work under a simplified model approach and directly take the$$\chi _\textrm{u}$$ χ u and$$\phi '$$ ϕ masses as free parameters. We perform a phenomenological analysis considering$$\chi _\textrm{u}$$ χ u final states to b-quarks, muons, and neutrinos, and$$\phi '$$ ϕ decays to$$\mu ^+\mu ^-$$ μ + μ - . A machine learning algorithm is used to maximize the signal sensitivity, considering an integrated luminosity of 3000$$\text {fb}^{-1}$$ fb - 1 . The proposed methodology can be a key mode for discovery over a large mass range, including low masses, traditionally considered difficult due to experimental constraints. 
    more » « less