Woojin Kim
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Woojin Kim has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Facundo Mémoli
DEPARTMENT OF MATHEMATICS RUTGERS UNIVERSITY
6 shared publications - Samantha Moore
Department of Mathematics, North Carolina School of Science and Mathematics- Morganton, Morganton, USA
2 shared publications - Anastasios Stefanou
Department of Mathematics and Computer Science University of Bremen 28359 Bremen Germany
1 shared publication Dong Soo Cho
School of Aerospace and Mechanical Engineering, Seoul National University, Seoul, South Korea
1 shared publicationH. Jin Kim
School of Aerospace and Mechanical Engineering, Seoul National University, Seoul, South Korea
1 shared publication- Nathaniel Clause
The Ohio State University Columbus OH
1 shared publication
Latest Publications
- Open Access
- 28 June 2024
- Published by Springer Nature in Journal of Applied and Computational Topology
- Vol. 8 (3) , 727-760
Bigraded Betti numbers and generalized persistence diagrams
Commutative diagrams of vector spaces and linear maps over $$\mathbb {Z}^2$$ are objects of interest in topological data analysis (TDA) where this type of diagrams are called 2-parameter persistence modules. Given that quiver representation theory tells us that such diagrams are of wild type, studying informative invariants of a 2-parameter persistence module M is of central importance in TDA. One of such invariants is the generalized rank invariant, recently introduced by Kim and Mémoli. Via the Möbius inversion of the generalized rank invariant of M, we obtain a collection of connected subsets $$I\subset \mathbb {Z}^2$$ with signed multiplicities. This collection generalizes the well known notion of persistence barcode of a persistence module over $$\mathbb {R}$$ from TDA. In this paper we show that the bigraded Betti numbers of M, a classical algebraic invariant of M, are obtained by counting the corner points of these subsets Is. Along the way, we verify that an invariant of 2-parameter persistence modules called the interval decomposable approximation (introduced by Asashiba et al.) also encodes the bigraded Betti numbers in a similar fashion. We also show that the aforementioned results are optimal in the sense that they cannot be extended to d-parameter persistence modules for $$d \ge 3$$ .- 28 June 2024
- Published by Springer Nature in Journal of Applied and Computational Topology
- Vol. 8 (3) , 727-760
Open AccessBigraded Betti numbers and generalized persistence diagrams
Commutative diagrams of vector spaces and linear maps over $$\mathbb {Z}^2$$ are objects of interest in topological data analysis (TDA) where this type of diagrams are called 2-parameter persistence modules. Given that quiver representation theory tells us that such diagrams are of wild type, studying informative invariants of a 2-parameter persistence module M is of central importance in TDA. One of such invariants is the generalized rank invariant, recently introduced by Kim and Mémoli. Via the Möbius inversion of the generalized rank invariant of M, we obtain a collection of connected subsets $$I\subset \mathbb {Z}^2$$ with signed multiplicities. This collection generalizes the well known notion of persistence barcode of a persistence module over $$\mathbb {R}$$ from TDA. In this paper we show that the bigraded Betti numbers of M, a classical algebraic invariant of M, are obtained by counting the corner points of these subsets Is. Along the way, we verify that an invariant of 2-parameter persistence modules called the interval decomposable approximation (introduced by Asashiba et al.) also encodes the bigraded Betti numbers in a similar fashion. We also show that the aforementioned results are optimal in the sense that they cannot be extended to d-parameter persistence modules for $$d \ge 3$$ . - Open Access
The Generalized Rank Invariant: Möbius invertibility, Discriminating Power, and Connection to Other Invariants
Unlike one-parameter persistent homology, the absence of a canonical method for quantifying `persistence' in multiparameter persistent homology remains a hurdle in its application. One of the best known quantifications of persistence for multiparameter persistent homology is the rank invariant, which has recently evolved into the generalized rank invariant by naturally extending its domain. This extension enables us to quantify 'persistence' across a broader range of regions in the indexing poset compared to the rank invariant. However, the size of the domain of the generalized rank invariant is generally formidable, making it desirable to restrict its domain to a more manageable subset for computational purposes. The foremost questions regarding such a restriction of the domain are: (1) How to restrict, if possible, the domain of the generalized rank invariant without any loss of information? (2) When can we more compactly encode the generalized rank invariant as a `persistence diagram'? (3) What is the trade-off between computational efficiency and the discriminating power of the generalized rank invariant as the amount of the restriction on the domain varies? To address these questions, we generalize and axiomatize the classic fundamental lemma of persistent homology via the notion of M\"obius invertibility of the generalized rank invariant which we propose. This extension also contextualizes known results regarding the (generalized) rank invariant within the classical theory of M\"obius inversion. We conduct a comprehensive comparison between M\"obius invertibility and other existing concepts related to the structural simplicity of persistence modules, such as Miller's notion of tameness. During this investigation, we identify an example of a persistence module whose generalized rank invariant is not M\"obius invertible.
Open AccessThe Generalized Rank Invariant: Möbius invertibility, Discriminating Power, and Connection to Other Invariants
Unlike one-parameter persistent homology, the absence of a canonical method for quantifying `persistence' in multiparameter persistent homology remains a hurdle in its application. One of the best known quantifications of persistence for multiparameter persistent homology is the rank invariant, which has recently evolved into the generalized rank invariant by naturally extending its domain. This extension enables us to quantify 'persistence' across a broader range of regions in the indexing poset compared to the rank invariant. However, the size of the domain of the generalized rank invariant is generally formidable, making it desirable to restrict its domain to a more manageable subset for computational purposes. The foremost questions regarding such a restriction of the domain are: (1) How to restrict, if possible, the domain of the generalized rank invariant without any loss of information? (2) When can we more compactly encode the generalized rank invariant as a `persistence diagram'? (3) What is the trade-off between computational efficiency and the discriminating power of the generalized rank invariant as the amount of the restriction on the domain varies? To address these questions, we generalize and axiomatize the classic fundamental lemma of persistent homology via the notion of M\"obius invertibility of the generalized rank invariant which we propose. This extension also contextualizes known results regarding the (generalized) rank invariant within the classical theory of M\"obius inversion. We conduct a comprehensive comparison between M\"obius invertibility and other existing concepts related to the structural simplicity of persistence modules, such as Miller's notion of tameness. During this investigation, we identify an example of a persistence module whose generalized rank invariant is not M\"obius invertible.
- Open Access
Bigraded Betti numbers and Generalized Persistence Diagrams
Commutative diagrams of vector spaces and linear maps over $\mathbb{Z}^2$ are objects of interest in topological data analysis (TDA) where this type of diagrams are called 2-parameter persistence modules. Given that quiver representation theory tells us that such diagrams are of wild type, studying informative invariants of a 2-parameter persistence module $M$ is of central importance in TDA. One of such invariants is the generalized rank invariant, recently introduced by Kim and M\'emoli. Via the M\"obius inversion of the generalized rank invariant of $M$, we obtain a collection of connected subsets $I\subset\mathbb{Z}^2$ with signed multiplicities. This collection generalizes the well known notion of persistence barcode of a persistence module over $\mathbb{R}$ from TDA. In this paper we show that the bigraded Betti numbers of $M$, a classical algebraic invariant of $M$, are obtained by counting the corner points of these subsets $I$s. Along the way, we verify that an invariant of 2-parameter persistence modules called the interval decomposable approximation (introduced by Asashiba et al.) also encodes the bigraded Betti numbers in a similar fashion. We also show that the aforementioned results are optimal in the sense that they cannot be extended to $d$-parameter persistence modules for $d \geq 3$.Open AccessBigraded Betti numbers and Generalized Persistence Diagrams
Commutative diagrams of vector spaces and linear maps over $\mathbb{Z}^2$ are objects of interest in topological data analysis (TDA) where this type of diagrams are called 2-parameter persistence modules. Given that quiver representation theory tells us that such diagrams are of wild type, studying informative invariants of a 2-parameter persistence module $M$ is of central importance in TDA. One of such invariants is the generalized rank invariant, recently introduced by Kim and M\'emoli. Via the M\"obius inversion of the generalized rank invariant of $M$, we obtain a collection of connected subsets $I\subset\mathbb{Z}^2$ with signed multiplicities. This collection generalizes the well known notion of persistence barcode of a persistence module over $\mathbb{R}$ from TDA. In this paper we show that the bigraded Betti numbers of $M$, a classical algebraic invariant of $M$, are obtained by counting the corner points of these subsets $I$s. Along the way, we verify that an invariant of 2-parameter persistence modules called the interval decomposable approximation (introduced by Asashiba et al.) also encodes the bigraded Betti numbers in a similar fashion. We also show that the aforementioned results are optimal in the sense that they cannot be extended to $d$-parameter persistence modules for $d \geq 3$. - 11 October 2023
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (4) , 1276-1342
Extracting Persistent Clusters in Dynamic Data via Möbius Inversion
- 11 October 2023
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (4) , 1276-1342
Extracting Persistent Clusters in Dynamic Data via Möbius Inversion
- Open Access
- 7 October 2023
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (1) , 67-94
Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications
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 interval I of a $$\textbf{Z}^2$$ -indexed persistence module M is equal to the generalized rank of the zigzag module that is induced on a certain path in I tracing mostly its boundary. Hence, we can compute the generalized rank of M over I by computing the barcode of the zigzag module obtained by restricting to that path. If M is the homology of a bifiltration F of $$t$$ simplices (while accounting for multi-criticality) and I consists of $$t$$ points, this computation takes $$O(t^\omega )$$ time where $$\omega \in [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 module M, determine whether M is interval decomposable and, if so, compute all intervals supporting its indecomposable summands.- 7 October 2023
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (1) , 67-94
Open AccessComputing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications
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 interval I of a $$\textbf{Z}^2$$ -indexed persistence module M is equal to the generalized rank of the zigzag module that is induced on a certain path in I tracing mostly its boundary. Hence, we can compute the generalized rank of M over I by computing the barcode of the zigzag module obtained by restricting to that path. If M is the homology of a bifiltration F of $$t$$ simplices (while accounting for multi-criticality) and I consists of $$t$$ points, this computation takes $$O(t^\omega )$$ time where $$\omega \in [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 module M, determine whether M is interval decomposable and, if so, compute all intervals supporting its indecomposable summands. - 8 September 2023
- Published by Springer Nature in Order
- Vol. 41 (2) , 497-537
Interleaving by Parts: Join Decompositions of Interleavings and Join-Assemblage of Geodesics
- 8 September 2023
- Published by Springer Nature in Order
- Vol. 41 (2) , 497-537
Interleaving by Parts: Join Decompositions of Interleavings and Join-Assemblage of Geodesics
- 26 June 2020
- Published by Springer Nature
- p. 371-389
Analysis of Dynamic Graphs and Dynamic Metric Spaces via Zigzag Persistence
- 26 June 2020
- Published by Springer Nature
- p. 371-389
Analysis of Dynamic Graphs and Dynamic Metric Spaces via Zigzag Persistence
- Top Cited Papers
- 2 February 2020
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 66 (3) , 831-875
Spatiotemporal Persistent Homology for Dynamic Metric Spaces
- 2 February 2020
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 66 (3) , 831-875
Top Cited PapersSpatiotemporal Persistent Homology for Dynamic Metric Spaces
- 1 October 2010
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 938-942
Sequential multi-agent task assignment using auction algorithm based on D∗ lite
In this paper, we study task assignment strategy for multi-agent systems in which the task space grows sequentially. Many task assignment algorithms are based on the heuristic schemes that result in optimal performance, but in time-varying conditions, real-time assignment techniques are needed. In order to maximize the real-time performance, an auction algorithm is adopted and modified with D* lite algorithm to handle various events and changes of environments. The numerical results show that the proposed approach can be solved in real-time for various scenario and can perform sequential tasks efficiently. The extensions and possible applications of the approach are also discussed.
- 1 October 2010
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 938-942
Sequential multi-agent task assignment using auction algorithm based on D∗ lite
In this paper, we study task assignment strategy for multi-agent systems in which the task space grows sequentially. Many task assignment algorithms are based on the heuristic schemes that result in optimal performance, but in time-varying conditions, real-time assignment techniques are needed. In order to maximize the real-time performance, an auction algorithm is adopted and modified with D* lite algorithm to handle various events and changes of environments. The numerical results show that the proposed approach can be solved in real-time for various scenario and can perform sequential tasks efficiently. The extensions and possible applications of the approach are also discussed.