Publication:2391709

DOI10.1145/2261250.2261286zbMath1280.55005arXiv1203.6786OpenAlexW2568390795MaRDI QIDQ2391709

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(nlog n)$ 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

zbMATH Keywords

doubling dimensionpersistent homologynet-treesVietoris-Rips filtrationmetric spanners

Mathematics Subject Classification ID

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

Cites Work

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

Related Items (30)

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

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