skip to main content

Search for: All records

Creators/Authors contains: "Kim, Woojin"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Free, publicly-accessible full text available September 1, 2024
  2. Free, publicly-accessible full text available September 8, 2024
  3. Abstract

    The notion of generalized rank in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. However, its efficient computation has not yet been studied in the literature. We show that the generalized rank over a finite intervalIof a$$\textbf{Z}^2$$Z2-indexed persistence moduleMis equal to the generalized rank of the zigzag module that is induced on a certain path inItracing mostly its boundary. Hence, we can compute the generalized rank ofMoverIby computing the barcode of the zigzag module obtained by restricting to that path. IfMis the homology of a bifiltrationFof$$t$$tsimplices (while accounting for multi-criticality) andIconsists of$$t$$tpoints, this computation takes$$O(t^\omega )$$O(tω)time where$$\omega \in [2,2.373)$$ω[2,2.373)is the exponent of matrix multiplication. We apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a moduleM, determine whetherMis interval decomposable and, if so, compute all intervals supporting its indecomposable summands.

    more » « less
  4. Characterizing the dynamics of time-evolving data within the framework of topological data analysis (TDA) has been attracting increasingly more attention. Popular instances of time-evolving data include flocking/swarming behaviors in animals and social networks in the human sphere. A natural mathematical model for such collective behaviors is a dynamic point cloud, or more generally a dynamic metric space (DMS). In this paper we extend the Rips filtration stability result for (static) metric spaces to the setting of DMSs. We do this by devising a certain three-parameter “spatiotemporal” filtration of a DMS. Applying the homology functor to this filtration gives rise to multidimensional persistence module derived from the DMS. We show that this multidimensional module enjoys stability under a suitable generalization of the Gromov–Hausdorff distance which permits metrization of the collection of all DMSs. On the other hand, it is recognized that, in general, comparing two multidimensional persistence modules leads to intractable computational problems. For the purpose of practical comparison of DMSs, we focus on both the rank invariant or the dimension function of the multidimensional persistence module that is derived from a DMS. We specifically propose to utilize a certain metric d for comparing these invariants: In our work this d is either (1) a certain generalization of the erosion distance by Patel, or (2) a specialized version of the well-known interleaving distance. In either case, the metric d can be computed in polynomial time. 
    more » « less