# Geometric Localization of Homology Cycles

arXiv: https://arxiv.org/abs/2406.03183 · HTML: https://mlsanity.com/paper/2406.03183/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 5 Jun 2024.

## Builds on (most cited first, 8 of 8)

- [Volume Optimal Cycle: Tightest representative cycle of a generator on persistent homology](https://mlsanity.com/paper/1712.05103/) (2017)
- [Persistent 1-Cycles: Definition, Computation, and Its Application](https://mlsanity.com/paper/1810.04807/) (2018)
- [Minimal Cycle Representatives in Persistent Homology using Linear Programming: an Empirical Study with User's Guide](https://mlsanity.com/paper/2105.07025/) (2021)
- [Computing Minimal Persistent Cycles: Polynomial and Hard Cases](https://mlsanity.com/paper/1907.04889/) (2019)
- [Minimum cycle and homology bases of surface embedded graphs](https://mlsanity.com/paper/1607.05112/) (2016)
- [Minimum bounded chains and minimum homologous chains in embedded simplicial complexes](https://mlsanity.com/paper/2003.02801/) (2020)
- [Stable Volumes for Persistent Homology](https://mlsanity.com/paper/2109.11711/) (2021)
- [On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class](https://mlsanity.com/paper/2112.02380/) (2021)

## Abstract (arXiv)

Computing an optimal cycle in a given homology class, also referred to as the homology localization problem, is known to be an NP-hard problem in general. Furthermore, there is currently no known optimality criterion that localizes classes geometrically and admits a stability property under the setting of persistent homology. We present a geometric optimization of the cycles that is computable in polynomial time and is stable in an approximate sense. Tailoring our search criterion to different settings, we obtain various optimization problems like optimal homologous cycle, minimum homology basis, and minimum persistent homology basis. In practice, the (trivial) exact algorithm is computationally expensive despite having a worst case polynomial runtime. Therefore, we design approximation algorithms for the above problems and study their performance experimentally. These algorithms have reasonable runtimes for moderate sized datasets and the cycles computed by these algorithms are consistently of high quality as demonstrated via experiments on multiple datasets.