Improved approximate Rips filtrations with shifted integer lattices

DOI10.4230/LIPICS.ESA.2017.28zbMATH Open1442.68244arXiv1706.07399MaRDI QIDQ5111715FDOQ5111715

Authors: Aruni Choudhary, Michael Kerber, Sharath Raghvendra 

Publication date: 27 May 2020

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.

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

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
• Linear-size approximations to the Vietoris-Rips filtration
• Linear-size approximations to the Vietoris-Rips filtration
• Polynomial-sized topological approximations using the permutahedron

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)

Cites Work

• Topology and data
• Computational topology. An introduction
• Topological persistence and simplification
• Title not available (Why is that?)
• Categorification of persistent homology
• Proximity of persistence modules and their diagrams
• A simple randomized sieve algorithm for the closest-pair problem
• Metrics for generalized persistence modules
• Computing Topological Persistence for Simplicial Maps
• Linear-size approximations to the Vietoris-Rips filtration
• Approximating persistent homology in Euclidean space through collapses
• Polynomial-Sized Topological Approximations Using The Permutahedron
• Visualizing Sparse Filtrations.
• Approximate Čech Complex in Low and High Dimensions
• Barcodes of Towers and a Streaming Algorithm for Persistent Homology
• Improved Approximate Rips Filtrations with Shifted Integer Lattices

Cited In (3)

• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• Improved Approximate Rips Filtrations with Shifted Integer Lattices
• Persistent homology in \(\ell_\infty\) metric

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)