Linear-size approximations to the Vietoris-Rips filtration

DOI10.1145/2261250.2261286zbMATH Open1280.55005arXiv1203.6786OpenAlexW2568390795MaRDI QIDQ2391709FDOQ2391709

Authors: Donald R. Sheehy 

Publication date: 5 August 2013

Published in: Discrete \& Computational Geometry, Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: The Vietoris-Rips filtration is a versatile tool in topological data analysis. It is a sequence of simplicial complexes built on a metric space to add topological structure to an otherwise disconnected set of points. It is widely used because it encodes useful information about the topology of the underlying metric space. This information is often extracted from its so-called persistence diagram. Unfortunately, this filtration is often too large to construct in full. We show how to construct an O(n)-size filtered simplicial complex on an $n$-point metric space such that its persistence diagram is a good approximation to that of the Vietoris-Rips filtration. This new filtration can be constructed in $O(nlogn)$ time. The constant factors in both the size and the running time depend only on the doubling dimension of the metric space and the desired tightness of the approximation. For the first time, this makes it computationally tractable to approximate the persistence diagram of the Vietoris-Rips filtration across all scales for large data sets. We describe two different sparse filtrations. The first is a zigzag filtration that removes points as the scale increases. The second is a (non-zigzag) filtration that yields the same persistence diagram. Both methods are based on a hierarchical net-tree and yield the same guarantees.

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

Recommendations

• Linear-size approximations to the Vietoris-Rips filtration
• The Persistent Homology of Cyclic Graphs
• Topological inference via meshing
• Divisive cover
• Efficient and robust persistent homology for measures
• SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch-collapse
• SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch collapse
• Approximating persistent homology in Euclidean space through collapses
• Optimal reconstruction might be hard
• Topological graph persistence

zbMATH Keywords

persistent homologydoubling dimensionmetric spannersnet-treesVietoris-Rips filtration

Mathematics Subject Classification ID

Simplicial sets and complexes in algebraic topology (55U10) Homology and cohomology theories in algebraic topology (55N99)

Cites Work

• Towards persistence-based reconstruction in euclidean spaces
• Topology and data
• Computational topology. An introduction
• Geometric inference for probability measures
• Stability of persistence diagrams
• Computing persistent homology
• Topological persistence and simplification
• Title not available (Why is that?)
• Zigzag persistent homology in matrix multiplication time
• Efficient data structure for representing and simplifying simplicial complexes in high dimensions
• The tidy set
• On the local behavior of spaces of natural images
• Zigzag persistence
• Coverage in sensor networks via persistent homology
• Geometric Spanner Networks
• Proximity of persistence modules and their diagrams
• Homological sensor networks
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Building triangulations using ε-nets
• Deformable spanners and applications
• Zigzag persistent homology and real-valued functions
• Nearest neighbor queries in metric spaces
• Title not available (Why is that?)
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Searching dynamic point sets in spaces with bounded doubling dimension
• Manifold reconstruction in arbitrary dimensions using witness complexes
• Topological inference via meshing

Cited In (32)

• Divisive cover
• Title not available (Why is that?)
• Sparse Dowker nerves
• A comparison framework for interleaved persistence modules
• Barcodes of towers and a streaming algorithm for persistent homology
• Linear-size approximations to the Vietoris-Rips filtration
• Quantitative simplification of filtered simplicial complexes
• MORSE REDUCTION FOR ZIGZAG COMPLEXES
• Alpha magnitude
• Polynomial-sized topological approximations using the permutahedron
• DTM-Based Filtrations
• Vietoris-Rips complexes of planar point sets
• Persistent homology for low-complexity models
• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• Strong Collapse for Persistence
• The Persistent Homology of Cyclic Graphs
• Improved Approximate Rips Filtrations with Shifted Integer Lattices
• Efficient and robust persistent homology for measures
• Universality of the homotopy interleaving distance
• Persistence Diagrams as Diagrams: A Categorification of the Stability Theorem
• Zigzag zoology: Rips zigzags for homology inference
• An approximate nerve theorem
• SimBa
• Computing the multicover bifiltration
• Strong collapse and persistent homology
• The Offset Filtration of Convex Objects
• Graph induced complex on point data
• Approximating persistent homology in Euclidean space through collapses
• Adaptive approximation of persistent homology
• Generalized persistence algorithm for decomposing multiparameter persistence modules
• Computing Persistent Homology of Flag Complexes via Strong Collapses
• Compression for \(2\)-parameter persistent homology

This page was built for publication: Linear-size approximations to the Vietoris-Rips filtration

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