Improved approximate Rips filtrations with shifted integer lattices

DOI10.4230/LIPICS.ESA.2017.28MaRDI QIDQ5111715zbMATHFDO

Authors Aruni Choudhary, Michael Kerber, Sharath Raghvendra

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1706.07399

zbMATH Keywords

persistent homologytopological data analysisapproximation algorithmsRips filtrations

Mathematics Subject Classification ID

Persistent homology and applications, topological data analysis (55N31) Simplicial sets and complexes in algebraic topology (55U10) Approximation algorithms (68W25) Combinatorial aspects of simplicial complexes (05E45) Computational aspects of digital topology (68U03)

Abstract: Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes constitutes an expensive task because of a combinatorial explosion in the complex size. For $n$ points in $mathbb{R}^d$, we present a scheme to construct a $3sqrt2$-approximation of the multi-scale filtration of the $L_{i}nfty$-Rips complex, which extends to a $O(d^{0.25})$-approximation of the Rips filtration for the Euclidean case. The $k$-skeleton of the resulting approximation has a total size of $n{2}^{O(dlogk)}$. The scheme is based on the integer lattice and on the barycentric subdivision of the $d$-cube.

Recommendations

• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch collapse
• Polynomial-sized topological approximations using the permutahedron

Cites work

• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• A simple randomized sieve algorithm for the closest-pair problem
• Approximate Čech Complex in Low and High Dimensions
• Approximating persistent homology in Euclidean space through collapses
• Barcodes of towers and a streaming algorithm for persistent homology
• Categorification of persistent homology
• Computational topology. An introduction
• Computing topological persistence for simplicial maps (extended abstract)
• Improved approximate Rips filtrations with shifted integer lattices
• Metrics for generalized persistence modules
• Polynomial-sized topological approximations using the permutahedron
• Proximity of persistence modules and their diagrams
• Topological persistence and simplification
• Topology and data
• Visualizing Sparse Filtrations.

Cited in

(5)

• Polynomial-sized topological approximations using the permutahedron
• Polynomial-sized topological approximations using the permutahedron
• Improved approximate Rips filtrations with shifted integer lattices
• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• Persistent homology in \(\ell_\infty\) metric

Describes a project that uses

Uses Software

• Sophia

This page was built for publication: Improved approximate Rips filtrations with shifted integer lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111715)