Source-linked AI summary
Confidence sets for persistence diagrams
Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, Larry Wasserman, Sivaraman Balakrishnan, Aarti Singh
TL;DR
Persistent homology needs statistical methods to distinguish topological signal from noise when inferring a space’s homology from sampled data. The paper derives confidence sets and compares distance-based and density-based approaches, finding a robustness trade-off between them.
Problem
Persistent homology must infer a space’s homology from sampled data while distinguishing meaningful features from noise and avoiding an arbitrary single tuning parameter.
Method
The paper constructs confidence sets for persistence diagrams by estimating bottleneck-distance uncertainty and develops three distance-based methods plus a density-estimation method.
Results
The distance-based methods connect more directly to raw data, while density-based methods are less fragile and more robust to noise and outliers.
Takeaways & Limitations
Adding a confidence band around the diagonal provides a simple visualization for treating points inside the band as consistent with noise.
Takeaways & Limitations
The concentration method is fragile to its parameter ρ and can fail when density is low even in a small region.
Abstract
from arXiv · showhide
Persistent homology is a method for probing topological properties of point clouds and functions. The method involves tracking the birth and death of topological features (2000) as one varies a tuning parameter. Features with short lifetimes are informally considered to be "topological noise," and those with a long lifetime are considered to be "topological signal." In this paper, we bring some statistical ideas to persistent homology. In particular, we derive confidence sets that allow us to separate topological signal from topological noise.
1. Introduction.
The paper introduces persistent homology as a multiscale topological summary and develops confidence sets to distinguish persistent signal from noise.
- Persistent homology tracks the birth and death of connected components, tunnels, and voids as a tuning parameter varies.
- Persistence points far from the diagonal represent features that persist across a long interval of radii.
- The paper provides a confidence set for a target persistence diagram using bottleneck distance between an estimated diagram and candidate diagrams.
- The authors also study confidence sets for persistence diagrams of density upper level sets.
- A simple visualization separates noise from signal by adding a band around the persistence-diagram diagonal; points inside are consistent with noise.
- The paper presents simple synthetic examples as a proof of concept for introducing persistent homology to statisticians and deriving confidence sets.
Outline.
This outline defines notation for Euclidean geometry, distance functions, reach, level sets, and probability before developing persistent-homology methods.
- The paper defines asymptotic comparison notation, Euclidean balls, distance functions, reach, level sets, and probability notation.
2. Brief introduction to persistent homology.
Persistent homology summarizes how lower-level-set topology changes, encoding each feature by its birth and death and enabling multiscale analysis without selecting one radius.
- Persistent homology represents lower-level-set topology across increasing function values using points corresponding to feature birth and death.
- For distance functions, sublevel sets expand with radius, while connected components, tunnels, and voids can appear and disappear.
- Points near the diagonal have short lifetimes and are treated as topological noise, whereas long-lived features are the main objects of interest.
- Persistent homology assigns persistence values equal to the intervals over which nontrivial homology generators occur, avoiding selection of a single radius.
- The Čech filtration discretizes changing sublevel-set homology through complexes at critical radii and induced homology maps.
- The paper uses Vietoris–Rips complexes to compute confidence sets for persistence diagrams of distance functions.
- Bottleneck stability bounds persistence-diagram distance by the L∞ distance between input functions and reduces inference to bounding Hausdorff distance.
3. Statistical model.
The statistical model infers the topology of an unobserved manifold from sampled data, using distance-based persistence and assumptions that are later weakened to allow outliers.
- The sample’s homology need not equal the manifold’s homology, motivating inference from unions of sample-centered balls across radii.
- The model assumes an i.i.d. sample from a distribution supported on or near a d-dimensional subset of R^D.
- The baseline assumptions require a compact boundaryless manifold with positive reach and regular behavior of the local mass function.
- The target is the persistence diagram of the manifold distance function, estimated by the diagram of the sample distance function.
- Before Section 4.4, the analysis assumes known manifold dimension and noiseless support exactly on the manifold.
- The paper later allows outliers and estimates persistence through density upper level sets, whose methods are described as robust.
4. Confidence sets.
The paper develops confidence sets for persistence diagrams and several methods for separating topological signal from noise, including a simple diagonal-band visualization and a density-based approach.
- Confidence sets: The confidence set Cn contains persistence diagrams within bottleneck distance cn of the estimated diagram bP.It is defined as C = {Q:W∞(bP,Q) ≤ cn}.
- Confidence sets: A point is treated as noise when its cn-neighborhood intersects the diagonal; points outside the resulting band represent significant topological features.The equivalent visualization adds a band of width 2cn around the diagonal.
- Methods: The first three methods use persistence diagrams from the Čech complex, while the fourth uses density estimation.The methods are defined in this section and illustrated later.
- Method I: Subsampling: Subsampling can be applied despite the problem’s nonstandard asymptotic form, but it produces conservative confidence intervals.The approach differs from the usual setting in which a normalized estimator converges to a fixed distribution.
- Method II: Concentration of measure: The concentration-based method is fragile because it depends on ρ, and low density in even a small region can severely impair it.The paper explicitly describes this dependence as a major practical weakness.
- Method IV: Density estimation: The density-based method estimates a smooth density and constructs persistence diagrams from its upper level sets, with positive bandwidth preserving topological information.For small bandwidth, level sets can retain the correct topology even though smoothing prevents exact recovery of the original density.
Finite sample band.
The finite-sample approach approximates density-based persistence diagrams on a finite grid and constructs confidence bands around the resulting diagram. The band can be substantially tighter when the grid is not too fine, reflecting finite-resolution inference.
- The persistence diagram of the estimated density is used to approximate the diagram of the underlying density.
- A kernel density estimator is approximated by piecewise linear interpolation over a finite grid and triangulation.
- The finite-sample confidence band can be substantially tighter when the grid is not too fine.
- The method treats topological inference as occurring at a finite resolution.
- A sharper asymptotic bound is also available through large-sample theory, with the bootstrap offered as the simplest approach.
Asymptotic confidence band.
The asymptotic approach constructs density estimators from bootstrap samples and uses bootstrap quantiles to approximate confidence-band quantities. The density method is described as barely affected by outliers and robust when their mixture proportion vanishes.
- Bootstrap samples are used to construct density estimators and approximate the quantile needed for the confidence band.
- Finite Monte Carlo error from using B bootstrap repetitions can be made arbitrarily small.
- The analysis emphasizes fixed-bandwidth asymptotics, although bandwidths may decrease if nh_n^D/log n →∞.
- For a mixture P = πU + (1 −π)Q, the bottleneck distance between the persistence diagrams is at most π apart up to rescaling.
- When the outlier proportion π_n tends to zero, the density method is described as very robust.
5. Experiments.
The experiments apply confidence-band methods to synthetic circle and eyeglasses examples, showing both successful feature detection and sensitivity to sampling sparsity and outliers.
- Unit circle: For a uniform sample of 500 points on the unit circle, subsampling and concentration methods correctly identify one connected component and one loop as significant.The bootstrap density method also finds these two significant features.
- Truncated Normal circle: For a truncated Normal sample on the unit circle, concentration misses the loop, while shells and subsampling declare it significant.The sparse portion of the circle makes this example challenging.
- Eyeglasses curve: For the eyeglasses curve, subsampling declares both loops significant, whereas concentration detects only one.The uniform distribution does not satisfy the assumptions for the shells method.
- Outliers: With outliers, distance-based methods can declare topological features insignificant, while density-based methods remain insensitive to the outliers.The examples replicate the circle and eyeglasses settings with added outliers.
6. Proofs.
The proofs establish the probabilistic and geometric bounds underlying the confidence-band methods, using covering, packing, concentration, and sample-splitting arguments.
- Proof strategy: The proof section provides proofs of the theorems and lemmas introduced earlier.
- Geometric bounds: Covering and packing constructions control geometric complexity through finite collections of balls on the manifold.The arguments relate covering and packing sizes and use bounds depending on dimension and reach.
- Subsampling: The subsampling proof shows that, with high probability, every subsample of the specified size covers the manifold sufficiently for the required comparison.The contradiction argument uses packed balls containing no subsample points to violate the relevant Hausdorff bound.
- Concentration and density estimation: The concentration arguments bound empirical density-estimation errors and use events controlling sample coverage and local density estimates.These bounds support the asymptotic construction of confidence thresholds.
- Sample splitting: The proof of the sample-splitting theorem combines conditional probability measures with the preceding density and coverage bounds.
7. Conclusion.
The conclusion contrasts distance-based and density-based approaches: the former connect more directly to raw data, while the latter are less fragile to noise and outliers.
- Conclusion: Distance-based methods use the distance function to the data, whereas density-based methods use density estimation and smoothing.
- Conclusion: Density-based methods are more robust to noise and outliers, while distance-based methods are more directly connected to the raw data.
- Open questions and limitations: Future work includes uncertainty for barcode plots, power analysis, adaptive bandwidths, and confidence intervals for other topological parameters.
- Open questions and limitations: The experiments are a proof of concept, and detailed simulation studies are needed to determine when the methods work well.
- Open questions and limitations: The subsampling method is conservative because the subsample size satisfies b = o(n), producing bias of order H(S_b,M)−H(S_n,M).The authors conjecture that this bias can be adjusted.
- Open questions and limitations: The optimal bandwidth for density estimation remains open because standard L2-loss theory may not suit topological estimation.
Supplement to “Confidence sets for persistence diagrams”
The supplement introduces persistence homology and provides additional details on homology, simplicial complexes, and persistence-diagram stability.
- Supplement: The supplementary material gives a brief introduction to persistent homology and additional details about homology, simplicial complexes, and stability of persistence diagrams.