Skip to Main content Skip to Navigation
Journal articles

Linear-size approximations to the vietoris-rips filtration

Donald Sheehy 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
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 of-ten 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(n log n) time. The constant factors in both the size and the run-ning 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 di-agram 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 guar-antees.
Document type :
Journal articles
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/hal-01111878
Contributor : Steve Oudot <>
Submitted on : Saturday, January 31, 2015 - 7:23:01 PM
Last modification on : Saturday, January 27, 2018 - 1:30:40 AM
Long-term archiving on: : Wednesday, May 27, 2015 - 3:21:03 PM

File

sheehy13linear.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Donald Sheehy. Linear-size approximations to the vietoris-rips filtration. Discrete and Computational Geometry, Springer Verlag, 2013, pp.778-796. ⟨10.1145/2261250.2261286⟩. ⟨hal-01111878⟩

Share

Metrics

Record views

247

Files downloads

420