Topological Data Analysis (TDA) has emerged as a powerful framework for extracting the underlying shape of complex datasets. However, real-world data is frequently contaminated with outliers that can catastrophically disrupt traditional geometric methods. This paper by Chazal, Massart, and Michel provides a rigorous statistical foundation for the Distance to Measure (DTM), a robust alternative to standard distance functions. By deriving tight convergence rates, the authors link statistical performance directly to the local geometry of the data distribution.
The Challenge of Robustness in TDA
In TDA, researchers typically study the "sublevel sets" of a distance function—essentially examining the union of balls around data points to infer the underlying manifold. A significant limitation of the standard distance-to-set function is its extreme sensitivity to outliers; even a single point far from the main cluster can drastically alter the inferred topology, a phenomenon known as the Hausdorff distance problem.
To mitigate this, the Distance to Measure (DTM) was introduced. Rather than calculating the distance to the single nearest point, DTM averages the distances to a fraction $m$ of the total probability mass. While DTM is known to be stable in a global sense (using Wasserstein metrics), a precise understanding of its statistical convergence rates was previously missing. Earlier bounds were often too loose to explain how the mass parameter $m$ affects error in practical applications.
Methodology: A Local Perspective
The authors move beyond global stability arguments, adopting a local analysis of empirical processes. Their technical innovation centers on three key components:
- Quantile Reformulation: They demonstrate that the DTM can be expressed as an integral of the quantile function of the distance distribution from a point $x$ to the data. This allows the use of univariate statistical tools to solve a multivariate geometric problem.
- Local Empirical Process Theory: Instead of analyzing how the entire distribution shifts, the authors focus on the "tails" near zero—the points closest to $x$. They utilize sharp concentration inequalities, including the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality and specialized bounds for uniform empirical processes, to bound the deviation between the empirical DTM and the true DTM.
- Geometric Linking: The authors connect the "regularity" (smoothness) of the quantile function to classical geometric concepts such as $(a,b)$-standard measures, which describe the distribution of mass on a manifold.
Experimental Validation
The paper validates its theoretical findings using several synthetic geometric experiments designed to represent common challenges in TDA:
- Segment Experiment: A 1D line segment in $\mathbb{R}$.
- 2D Shape Experiment: A complex, hand-drawn closed curve in $\mathbb{R}^2$.
- Fish Experiment: A 2D surface point cloud of approximately 217,000 points in $\mathbb{R}^3$.
- Tangle Cube Experiment: A complex 3D manifold defined by an algebraic equation.
For each shape, three generative models were tested: Noiseless (uniform sampling), Clutter Noise (adding uniform background outliers), and Gaussian Convolution (adding "blur" to the points).
Key Insights and Results
Local Regularity and Convergence Rates
The speed at which an estimate improves as more data is added depends almost entirely on the "modulus of continuity" of the quantile function at zero. If the data is dense near the support, the DTM converges rapidly. While Wasserstein-based bounds often predict a slow rate of $n^{-1/d}$ (where $d$ is the dimension), this paper proves that a faster parametric rate of $1/\sqrt{n}$ is achievable under reasonable local assumptions.
The Role of the Mass Parameter $m$
The parameter $m$ acts as a smoothing factor. When $m$ is very small (often used to "clean" outliers), the error is dominated by local geometry. As $m$ increases, the estimate becomes more stable but potentially introduces more bias. The authors provide explicit upper bounds for the expected error of the empirical DTM, showing it is roughly proportional to $\frac{\omega_x(k/n)}{\sqrt{k}}$, where $n$ is the number of points, $k$ is the number of neighbors considered ($k \approx nm$), and $\omega_x$ is the local regularity.
Optimality
Using Le Cam’s lemma, the authors prove that their obtained rates are essentially optimal for small values of $k$. Numerical simulations across different noise models and dimensions confirm that their theoretical complexity function perfectly matches the observed error monotonicity.
Limitations and Future Work
While the paper provides a sup-norm bound, much of the analysis remains pointwise. Extending these results to more complex topological descriptors, such as persistence diagrams, is a natural next step. Additionally, choosing the "optimal" $m$ remains a challenge; because the error does not follow a simple monotonic path (often appearing U-shaped depending on noise), standard model selection tools are difficult to apply. Finally, while the current work assumes Euclidean space, the authors suggest the results can be adapted to general metric spaces, though explicit geometric constants would require re-derivation.
Summary updated