Source-linked AI summary
Subsampling Methods for Persistent Homology
Frédéric Chazal, Brittany Terese Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, Larry Wasserman
TL;DR
Persistent homology offers multiscale topological summaries, but direct computation can be prohibitive for large point clouds. This paper combines landscapes computed from subsamples and studies their stability and risk, showing that the average landscape is stable under measure perturbations in Wasserstein distance.
Problem
Direct persistent-homology computation can be prohibitive for large point clouds because of its combinatorial complexity.
Source: §3 · p. 4Method
The paper repeatedly subsamples m points, computes their persistence landscapes, and combines them using average or closest-sample estimators.
Source: §3 · p. 5Results
Takeaways & Limitations
The subsampling framework is computationally fast and provides stability results and risk bounds for its summaries and estimators.
Source: §7 · p. 8
Abstract
from arXiv · showhide
Persistent homology is a multiscale method for analyzing the shape of sets and functions from point cloud data arising from an unknown distribution supported on those sets. When the size of the sample is large, direct computation of the persistent homology is prohibitive due to the combinatorial nature of the existing algorithms. We propose to compute the persistent homology of several subsamples of the data and then combine the resulting estimates. We study the risk of two estimators and we prove that the subsampling approach carries stable topological information while achieving a great reduction in computational complexity.
1 Introduction
Persistent homology summarizes topological features across scales, but its computational cost can make analysis of large point clouds prohibitive. The paper proposes combining persistence landscapes from subsamples and studies their stability, risk, and practical computation.
Contribution and Related Work
- Subsampling several point clouds, computing each persistence landscape, and combining them addresses the computational cost of persistent homology on large point clouds.The paper describes persistent homology’s time and space complexity as a main obstacle to applying TDA to high-dimensional problems.Source: §1 · p. 1
- The average landscape is stable to perturbations of the underlying measure in the Wasserstein metric.Source: §1 · p. 1
- The empirical average landscape is unbiased for the expected subsample landscape and biased for the support landscape, but is robust to outliers.The support landscape is computationally expensive; the paper also proposes a closest-sample estimator that requires knowing the support.Source: §1 · p. 1
- The approach differs from Blumberg et al. (2014), whose fixed-size subsamples yield stable diagram distributions in the Gromov-Prohorov metric; this paper instead offers easily computed summaries for infeasible exact computations.Source: §1 · p. 2
Software
- The planned R package would provide persistent-homology algorithms through an R interface and include tools for statistical analysis, including the methods in this paper.Source: §1 · p. 2
2 Background
Persistent homology tracks how topological features change across a filtration of geometric complexes, and persistence landscapes summarize the resulting diagrams. This section introduces the complexes, diagrams, and landscapes used in the paper.
2.1 Geometric Complexes
- Rips_α(X) ⊆ Čech_α(X) ⊆ Rips_2α(X), while the α-complex is defined for X ⊂ R^d using empty-interior balls.Figure 1 shows the distance sublevelset, α-complex, Čech complex, and Rips complex; the last two include a tetrahedron.Source: §2.1 · p. 2, Figure 1 · p. 2
2.2 Persistence Diagrams
- A filtration is a nested sequence of complexes indexed by α, whose evolving topology persistent homology summarizes through feature birth and death times.Features farther from the diagram’s diagonal are described as more persistent; points near it can be interpreted as topological noise.Source: §2.2 · p. 3, §2.1 · p. 3
- Persistence diagrams represent each feature by its birth and death coordinates, and their stability bounds diagram change under perturbations of the underlying space.For sets embedded in the same metric space, the cited stability statement uses Hausdorff distance.Source: §2.2 · p. 3
2.3 Persistence Landscapes
- A persistence landscape summarizes the arrangement of tent-shaped functions associated with diagram points as a collection of functions.In Figure 2’s rotated axes, a diagram point’s x-coordinate is the feature’s average parameter value and its y-coordinate is its half-life; the cyan curve is λ(1,·).Source: §2.3 · pp. 3–4, Figure 2 · p. 4
3 The Multiple Samples Approach
The approach repeatedly samples m points, computes their persistence landscapes, and uses averages or a closest sample to approximate the landscape of the support. It targets large-data computation while establishing stability and risk analyses under stated assumptions.
3 The Multiple Samples Approach
- Each landscape function is one-Lipschitz, and landscape differences at fixed k and t are bounded by the bottleneck distance between diagrams.Source: §3 · p. 4
- The expected landscape is the pointwise expectation of random landscapes from m-point samples and is stable under perturbations of μ.Source: §3 · p. 4
- The average of n independent m-point-sample landscapes estimates the support landscape, with its bias analyzed separately from its variance.The empirical average estimates the expected landscape; the paper identifies the difference between that expectation and the support landscape as the bias component.Source: §3 · p. 4
- The closest-sample method selects an m-point sample nearest to the support in Hausdorff distance and uses its landscape to approximate the support landscape.This method requires the support of μ to be known.Source: §3 · pp. 4–5
- When direct computation on N points is prohibitive, repeatedly subsampling m ≪ N points provides a computationally faster route to estimating the support landscape.The paper gives costs O(exp(N)) for direct computation, O(n exp(m)) for average landscapes, and O(nmN + exp(m)) for the closest-sample method.Source: §3 · pp. 4–5
- The framework assumes a lower bound on μ(B(x,r)) for r > r_0, allowing r_0 > 0 to cover discrete measures.The paper focuses on k = 1, while stating that its results also hold for k > 1 and for silhouettes.Source: §3 · pp. 4–5
4 Stability of the Average Landscape
The section establishes stability for the expected landscape of repeated m-point samples and explains how that stability relates to the underlying measures. It also identifies a consequence for Wasserstein comparisons and a dependence on sample size m.
4 Stability of the Average Landscape
- For measures on a metric space of bounded diameter, the expected landscapes of m-point samples are stable with respect to Wasserstein distance.The section also states an extension to measures on different spaces using Gromov-Wasserstein distance.Source: §4 · p. 5
- This stability means the expected topological behavior of m-point samples carries information about the generating measure and yields a lower bound on Wasserstein distance.Source: §4 · p. 5
- The stability bound depends on m; as m grows, sampled sets approach the measures’ supports, whose topologies can differ even when the measures are close in Wasserstein distance.The text notes a similar dependence in Blumberg et al. (2014) for persistence diagrams under the Gromov-Prohorov metric.Source: §4 · pp. 5–6
- Under the standard assumption on both measures, a further bound compares expected landscapes using the Hausdorff distance between their supports.The displayed bound includes a constant depending on a and b.Source: §4 · p. 6
5 Risk Analysis
The section analyzes the risk of the average landscape and closest-sample estimators for the landscape associated with the support. It gives bounds under a standard assumption and discusses the rate and robustness trade-offs.
5 Risk Analysis
- The average landscape’s ℓ∞-risk is decomposed, and stability is used to relate the estimator to the support landscape.The analysis assumes the measure satisfies the (a, b, r0)-standard assumption to bound the bias.Source: §5 · p. 6
- If computing Hausdorff distance to the support is feasible, its expected value can be approximated by averaging over B independently drawn subsamples.Source: §5 · p. 6
- When r0 is negligible, the text gives n of order (m/log m)^(2/b) to control the average estimator’s risk, using a variance term of order 1/√n.Source: §5 · p. 6
- The closest-sample method’s risk can in principle be smaller than the average landscape method’s risk.Source: §5 · p. 7
- When r0 is negligible, the average and closest-sample methods have comparable rates; the average method is also robust to outliers.Source: §5 · p. 7
6 Experiments
The experiments apply subsampling to 3D shapes and magnetometer point clouds because computing persistent homology on the full samples is infeasible. They compare closest-subsample landscapes, average landscapes, and pairwise dissimilarities.
Experiments
- The experiments use subsampling because persistent homology on the full Vietoris–Rips filtrations is infeasible for the large point clouds.They draw subsamples of size m much smaller than N from the discrete uniform measures on the point clouds.Source: §6 · p. 7
3D Shapes
- For 4 shapes with 7K–40K vertices each, 100 subsamples of 300 points yield closest-subsample and average landscapes plus pairwise dissimilarities between average landscapes.The dissimilarity matrix reports pairwise ℓ∞ distances, which the text identifies as lower bounds for Wasserstein distances between the shapes’ discrete uniform measures.Source: §6 · p. 7, Figure 4 · p. 8
Magnetometer Data
- For 4 activities, each represented by 7,500 measurements, 80 subsamples of 200 points yield closest-subsample and average landscapes plus pairwise dissimilarities.The data come from one person’s left-leg magnetometer, sampled at 25 Hz; the dissimilarities are pairwise ℓ∞ distances between average landscapes.Source: §6 · p. 8, Figure 5 · p. 8
- The magnetometer example illustrates persistent homology on sensor data and notes its insensitivity to input orientation, unlike methods requiring exact sensor calibration.The reported illustration uses four activities performed by one person, rather than the dataset’s full set of 19 activities and eight people.Source: §6 · p. 8
7 Conclusion
The paper presents a subsampling framework for approximating a set’s persistent homology. It reports that the summaries are simple and computationally fast, with stability results and risk bounds for the proposed estimators.
7 Conclusion
- The framework approximates a set’s persistent homology using subsamples and is described as simple and computationally fast.The conclusion also reports stability results for the new summaries and risk bounds for the proposed estimators.Source: §7 · p. 8
- The authors plan to release implementation software and investigate other ways to speed up the computations.Source: §7 · p. 8
A Technical results
The technical appendix develops results used in the paper’s main theorems, including notation for maps from samples to diagrams and landscapes and lemmas concerning distances between measures and landscape summaries.
Technical results
- For a sample of size m, φ_m maps the sample to its persistence diagram, and ψ_m maps the diagram to its persistence landscape.The appendix also introduces conditions on metrics for comparing m-point samples and names Hausdorff distance and an Lp-distance as examples satisfying both conditions.Source: A Technical results · p. 10
- Under condition (C1), the appendix gives a Wasserstein-distance lemma for probability measures and notes that its bound is tight when one measure is a Dirac measure.Source: A Technical results · p. 10
- The appendix invokes Jensen’s inequality and landscape stability to relate expected landscape differences to expected bottleneck-distance costs.The corresponding lemmas address measures on the sample space and random persistence landscapes.Source: A Technical results · pp. 10–11
B Main Proofs
The proof of Theorem 5 is reduced to three inequalities: one for tensor-product measures, one for mapping measures from sample space to diagram space, and one for expected landscape differences.
B Main Proofs
- The proof of Theorem 5 combines an upper bound for Wasserstein distance between tensor-product measures with bounds for passing from measures on samples to diagrams and from diagrams to expected landscapes.Source: B Main Proofs · p. 12
Proof of Theorem 6
The appendix proofs use distance decompositions and casewise bounds, then discuss when the (a, b, r0)-standard assumption holds with high probability for discrete point clouds.
Proof of Theorem 6
- For Theorem 6, the proof sets ε0 = H(Xµ, Xν) and bounds H(X, Y) through distances involving Xµ and Xν.It handles one of the resulting cases, with the other treated similarly.Source: Proof of Theorem 6 · pp. 12–13
Proof of Theorem 9
- Theorem 9’s proof splits its bound according to whether rm ≤ r0 or rm > r0, using Lemma 14.The proof also invokes a strategy used for Theorem 2 in Chazal et al. (2014b).Source: Proof of Theorem 9 · p. 13
C About the (a, b, r0)-standard assumption
- For discrete uniform point clouds sampled from η, the (a, b, r0)-standard assumption holds with high probability as N grows under the stated finite-VC-dimension condition.The passage gives balls in Rd, with VC-dimension d+1, as an example.Source: C About the (a, b, r0)-standard… · p. 14
D Robustness to Outliers
The section examines robustness to outliers: average landscapes remain close in an example where raw landscapes differ, and filtering can further exclude outliers under stated conditions.
D Robustness to Outliers
- With one outlier replacing a circle point, the average landscapes are close although the raw landscapes differ; the two measures have 1-Wasserstein distance 1/N.Figure 6 compares the point sets, their dimension-1 persistence diagrams, and landscapes from 30 subsamples of size 100.Source: D Robustness to Outliers · p. 14, Figure 6 · p. 15
- The average-landscape estimator can be more accurate than both the closest-subsample method and the landscape from the full N-point sample when outliers are present.The setup defines β as the minimal bias among subsets containing at least one outlier.Source: D Robustness to Outliers · p. 14
- With outlier fraction ϵ, the closest subsample is infected with probability tending to one, and the selected landscape then has bias of order β.The passage gives the infection probability as 1 − (1 − ϵ)^nm ∼ 1 − e^−ϵnm.Source: D Robustness to Outliers · pp. 14, 16
- Filtered subsampling can exclude outliers with high probability when its density threshold lies between the stated outlier and good-observation bounds.The filtering example uses a kernel density estimator and assumes the good observations satisfy the (a, b)-standard condition with b < d and a > 0.Source: D Robustness to Outliers · p. 16