PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Topological Inference: Distance To a Measure and Kernel Distance

Frédéric Chazal, Brittany T. Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, Larry Wasserman

arXiv:1412.7197v1math.STcs.CGmath.AT

TL;DR

Persistent-homology inference from the empirical distance function is highly sensitive to noise and outliers. The paper studies robust alternatives—the DTM and kernel distance—deriving limiting distributions, bootstrap confidence sets, tuning-parameter selection, and boundary-bias corrections. It concludes that these methods can provide useful topological information while supporting statistical inference, although the smoothing parameters remain bounded away from zero and several practical procedures need further investigation.

  • Problem

    The empirical distance function is non-robust to noise and outliers, motivating statistical inference for robust topological measures such as the DTM and kernel distance.

  • Method

    The paper derives limiting distributions and bootstrap confidence sets for DTM and kernel-distance persistence, and proposes methods for selecting smoothing parameters and reducing boundary bias.

  • Results

    The bootstrap provides asymptotically valid confidence bands for the DTM, while the paper establishes analogous results for the kernel distance and a more precise bottleneck bootstrap under additional assumptions.

  • Takeaways & Limitations

    Confidence bands can separate topological signal from noise, and in the examples the DTM generally performs better than KDE under concentrated sampling around nodes and filaments.

  • Takeaways & Limitations

    The theory treats smoothing parameters as bounded away from zero, and the proposed methods for tuning-parameter choice and boundary-bias mitigation require further investigation.

Abstract

from arXiv · show

Let P be a distribution with support S. The salient features of S can be quantified with persistent homology, which summarizes topological features of the sublevel sets of the distance function (the distance of any point x to S). Given a sample from P we can infer the persistent homology using an empirical version of the distance function. However, the empirical distance function is highly non-robust to noise and outliers. Even one outlier is deadly. The distance-to-a-measure (DTM), introduced by Chazal et al. (2011), and the kernel distance, introduced by Phillips et al. (2014), are smooth functions that provide useful topological information but are robust to noise and outliers. Chazal et al. (2014) derived concentration bounds for DTM. Building on these results, we derive limiting distributions and confidence sets, and we propose a method for choosing tuning parameters.

1. Introduction.

The paper studies persistent-homology inference for support topology using robust distance-like functions, because the empirical distance function is vulnerable to noise and outliers. It develops statistical inference, tuning-parameter selection, and boundary-bias corrections for the DTM and kernel distance.

  • Topological motivation: Persistent homology summarizes multiscale features of a support, including connected components, loops, and voids, through sublevel-set evolution.Persistence diagrams record the birth and death times of these topological features.
  • Robustness problem: The empirical distance function is consistent under bounded-density assumptions but has breakdown point zero in the presence of outliers or noise.Even a few outliers can completely change the estimated distance function.
  • Robust methods: The distance-to-a-measure replaces the true measure with an empirical or deconvolved measure and builds persistence diagrams from its sublevel sets.This approach directly targets the persistent homology of the support while remaining robust to noise.
  • Statistical contributions: The paper derives asymptotically valid bootstrap confidence bands for the DTM, limiting distributions for bottleneck distance, and more precise bottleneck-bootstrap inference under additional assumptions.It also establishes analogous results for the kernel distance.
  • Extensions and practical choices: The authors propose selecting DTM and kernel-distance smoothing parameters by maximizing the total amount of significant persistence.The paper also discusses methods for reducing boundary bias, which affects both DTM and KDE.

2. Background.

Persistent homology describes the multiscale topology of a compact support through distance-function sublevel sets, but the empirical distance function is highly sensitive to noise and outliers. The DTM provides a smoother alternative whose empirical version is computed from nearest neighbors.

  • Distance Functions and Persistent Homology: Persistent homology tracks connected components, loops, and voids as distance-function sublevel sets expand with time.Features are represented by birth and death times in persistence diagrams.
  • Distance Functions and Persistent Homology: The bottleneck distance between persistence diagrams is bounded by the sup-norm difference between their distance functions, which equals the Hausdorff distance between supports.This is the persistence stability theorem.
  • Distance Functions and Persistent Homology: Under density bounds, the empirical distance function can estimate persistent homology through sublevel sets represented as unions of balls and Cech complexes.The union-of-balls filtration can be processed using linear-algebraic persistence computations.
  • Distance to a Measure: A few outliers can completely change the empirical distance function, giving it breakdown point zero even when contamination and noise are small.The contamination model combines an outlier distribution with a noisy distribution supported near S.
  • Distance to a Measure: The distance-to-measure is introduced as a robust alternative for recovering useful shape information when exact recovery is under-identified.Its empirical form uses the k nearest neighbors, with k = ⌈mn⌉.

2. If P satisfies (11) and is supported on a compact set S, then

For distributions satisfying the stated regularity condition, DTM distances are stable under Wasserstein perturbations and can approximate the support distance function. The resulting persistence diagrams inherit corresponding robustness bounds under contamination and noise.

  • DTM Properties: The DTM converges uniformly to the support distance function as its resolution m tends to zero.Specifically, sup_x |δP,m(x)−∆S(x)| → 0 as m → 0.
  • DTM Properties: DTM differences for two distributions are bounded by m^-1/2 times their Wasserstein-2 distance.This gives a direct perturbation bound for DTM functions.
  • DTM Properties: Choosing m ≍ W2(P,Q)^(2b/(2+b)) yields sup_x |δQ,m(x)−∆S(x)| = O(W2(P,Q)^(2/(2+b))).The bound balances DTM resolution against distributional perturbation.
  • DTM Properties: The paper concludes that the bottleneck distance between the DTM diagram and the support-distance diagram is bounded under the contamination model.The bound depends on the outlier-set radius, support radius, noise scale, and resolution.
  • DTM Properties: For the contamination model, the Wasserstein perturbation is bounded using separate transport costs for outliers and Gaussian noise.The transport construction couples the mixture to the noisy signal distribution.

3. Limiting Distribution of the Empirical DTM.

The paper derives pointwise and functional Gaussian limits for the empirical DTM under quantile-regularity assumptions, then uses bootstrap methods to construct confidence bands. The functional result holds for every fixed resolution m in (0,1), with a global rather than local regularity formulation.

  • Pointwise Limit: Under differentiability of the distance cdf at the relevant quantile, the empirical DTM has a pointwise Gaussian limit.The theorem establishes convergence after √n scaling for a fixed spatial point.
  • Functional Limit: The proof uses compact-domain covering arguments, Lipschitz control, quantile regularity, and the Donsker property of the associated function class.These ingredients establish uniform convergence over x in the compact domain.
  • Functional Limit: A uniform modulus of continuity for the family of distance quantile functions enables control over the DTM on a compact domain.The paper derives such a modulus under an absolute-continuity and positive-density assumption on pushed-forward distance measures.
  • Functional Limit: The functional limit is √n(bδ^2(x)−δ^2(x)) ⇝ B(x), a centered Gaussian process with an explicitly derived covariance kernel.The proof separates a negligible remainder from an empirical-process term converging to the Gaussian process.
  • Functional Limit: The stated functional limit applies globally for any m ∈ (0,1), rather than using a local modulus of continuity at m.The authors choose the global formulation for clarity.
  • Confidence Bands: Bootstrap methods are introduced to obtain confidence bands for the DTM.The construction is based on the limiting-process framework developed in the preceding results.

4. Hadamard Differentiability and The Bootstrap.

The section establishes asymptotic and bootstrap results for the empirical DTM by proving Hadamard differentiability and applying the functional delta method under regularity assumptions.

  • Asymptotic theory: The empirical DTM process converges to a centered Gaussian process under compact support and differentiability assumptions on FP,x at F−1x(m).The proof uses the Donsker property of closed Euclidean balls and the functional delta method.
  • Bootstrap validity: The bootstrap process converges conditionally in probability to the same Gaussian limit as the original empirical DTM process.The result supports bootstrap inference for the DTM function.
  • Assumptions: The analysis compares two regularity conditions on the quantile functions: uniform modulus of continuity and a uniform lower bound on derivatives.The latter condition used in Theorem 11 is stronger, although both require the quantile functions to be well behaved near m.
  • Proof strategy: The proof represents signed measures through their evaluations on closed balls, placing the empirical process in a normed function space where Donsker convergence applies.This representation enables the delta-method argument for bootstrap validity.
  • Hadamard differentiability: The mapping from a probability measure to the squared DTM is Hadamard differentiable at P.This differentiability transfers empirical-process convergence to the DTM through the functional delta method.
  • Bootstrap validity: The bootstrap estimate bcα consistently estimates the limiting critical value cα.This yields asymptotically valid bootstrap confidence sets for the DTM.

5. Theory for Kernels.

The section develops limiting theory for kernel distance and relates its sublevel sets to kernel density estimation. Its bootstrap limit justifies confidence bands and persistence-based inference.

  • Kernel distance: Kernel distance can be represented as a norm between feature vectors in an appropriate reproducing kernel Hilbert space.This connects the method to a standard machine-learning distance construction.
  • Kernel specification: The Gaussian kernel K_h has one tuning parameter, h, which is generally held fixed for topological inference.The section explicitly cautions against letting h tend to zero in this setting.
  • Connection to density estimation: Up to small-order terms, kernel-distance sublevel sets are rescaled versions of kernel-density-estimator super-level sets.Thus, the kernel-distance and density-estimation approaches are essentially equivalent up to rescaling for topological inference.
  • Comparison with DTM: The kernel-distance conditions required for limiting behavior are weaker than those required for the DTM.This comparison is stated directly in the section’s kernel theory.
  • Limiting behavior: The kernel-distance estimator has a Gaussian-process limiting distribution, and its bootstrap version converges to the same limit conditionally almost surely.The Gaussian process is described using a Brownian bridge.
  • Bootstrap inference: The bootstrap supports construction of L∞ bands for the kernel density estimator and the kernel distance.The theorem provides the asymptotic justification for these bands.

6. The Bottleneck Bootstrap.

The bottleneck bootstrap yields asymptotically valid, feature-specific confidence bands by exploiting the limiting behavior of persistence-diagram bottleneck distances under regularity assumptions.

  • The bootstrap quantile is estimated by Monte Carlo and used to construct a band of size 2b_tα around the persistence diagram.
  • Bottleneck bootstrap bands can be more precise than functional-bootstrap bands because they avoid potentially conservative sup-norm bounds and can vary by homology dimension.
  • Critical-point stability ensures nearby Morse functions have the same number and indices of critical points under the stated separation and smoothness conditions.
  • Under the critical-distance conditions, the bottleneck distance equals the maximum displacement b of corresponding critical values.
  • The paper derives the limiting distribution of the scaled bottleneck distance for persistence diagrams formed from a kernel density estimator.
  • Uniform concentration of estimated gradients and Hessians supports the asymptotic control of estimated critical points.

7. Extensions.

The extensions address smoothing-parameter selection, boundary bias, and noise or outlier reduction for robust topological inference.

  • 7.1. A Method for Choosing the Smoothing Parameter: The smoothing parameter is selected by maximizing either the number or total persistence of significant features.
  • 7.1. A Method for Choosing the Smoothing Parameter: The selection criteria exhibit a topological bias-variance trade-off: small parameters retain unstable features, whereas large parameters smooth features away.
  • 7.2. Boundary Bias: Boundary bias can produce incomplete loops, causing DTM and KDE to miss topological features near the boundary.
  • 7.2. Boundary Bias: Adding points uniformly around the boundary closes boundary loops and provides a simple correction for topological inference.
  • 7.2. Boundary Bias: In the Voronoi example, adding 2,000 boundary points increases the detected significant loops from 9 to 16.
  • 7.3. Outliers and Noise: Outliers can be reduced by truncating low-density observations before re-estimating the density.
  • 7.3. Outliers and Noise: Data sharpening moves observations along the estimated density gradient, reducing bias at density peaks and potentially clarifying topological features.
  • 7.3. Outliers and Noise: For the noisy grid, density filtering and sharpening reduce noise-related persistence features in the resulting diagrams.

8. Examples.

Examples apply DTM, kernel distance, and KDE to noisy grids, soccer tracking data, and Voronoi models, illustrating robust topological recovery and comparative behavior.

  • Noisy Grid: In the noisy-grid experiment, 10,000 grid points receive Gaussian noise and 1,000 outliers before persistence diagrams and bootstrap confidence sets are computed.
  • Noisy Grid: Persistence diagrams and bootstrap confidence bands separate topological signal from noise across the example models.
  • Soccer: In soccer tracking data, boundary points are added to avoid boundary bias, and DTM and kernel-distance diagrams compare defender and midfielder movement patterns.
  • Voronoi Models: Voronoi wall, filament, and cluster models are generated by sampling around faces, lines, and nodes of Voronoi diagrams.
  • Voronoi Models: Voronoi experiments add Gaussian noise and boundary points, then compare persistence diagrams for the distance function, DTM, and KDE.
  • Persistent Homology: The diagrams represent a filtration in which connected components appear first, merge into loops, and later evolve into three-dimensional voids.
  • Comparisons: The DTM generally performs better than KDE because KDE is more affected by high point density around nodes and filaments.

9. Discussion.

The discussion contrasts KDE and DTM as complementary tools with different topological goals, reviews alternative level-set inference assumptions, and identifies parameter selection, boundary correction, and data sharpening as areas needing further work.

  • Comparison of DTM and Kernel Distance: KDE and DTM both extract topological features, but KDE probes the homology of S through density upper level sets whereas DTM estimates persistent homology of S.Their broad aim is shared, but their inferential targets differ.
  • Comparison of DTM and Kernel Distance: Varying KDE bandwidth or DTM parameter m could extract additional information, but the authors leave these possibilities for future work.The paper specifically suggests examining {p_h > t} across h and DTM persistence across m.
  • Alternative Topological Inference: A single-level robust approach assumes some density upper level set is homotopic to S across an interval of thresholds, an assumption that can hold for small S, mixture weight π, and noise scale σ.Under this condition, persistent homology can also recover dominant features corresponding to the homology of S.
  • Alternative Topological Inference: The single-level approach additionally assumes known dimension k and vanishing kth homology rank above a threshold; the strength of this assumption remains unclear.The authors plan to compare its robustness with persistent homology.
  • Future Work: Choosing tuning parameters, mitigating boundary bias, and sharpening data all remain issues requiring further investigation.The paper also points toward future hypothesis tests for comparing point clouds in a companion work.
Loading 1412.7197v1…