Witnessed k-Distance

Leonidas J. Guibas, Quentin Mérigot, Dmitriy Morozov

Abstract

Distance function to a compact set plays a central role in several areas of computational geometry. Methods that rely on it are robust to the perturbations of the data by the Hausdorff noise, but fail in the presence of outliers. The recently introduced distance to a measure offers a solution by extending the distance function framework to reasoning about the geometry of probability measures, while maintaining theoretical guarantees about the quality of the inferred information. A combinatorial explosion hinders working with distance to a measure as an ordinary (power) distance function. In this paper, we analyze an approximation scheme that keeps the representation linear in the size of the input, while maintaining the guarantees on the inference quality close to those for the exact (but costly) representation.

Introduction

In computational geometry and topological data analysis (TDA), understanding the "shape" of a point cloud is a fundamental task. Traditional methods often rely on the distance to the nearest point in a set. While effective for clean data, these methods are notoriously sensitive to outliers; a single distant point can erroneously fill a topological hole or merge distinct components.

To address this, the "distance to a measure" (DTM) was introduced, which considers the average distance to the $k$ nearest neighbors. While DTM is mathematically robust to noise, its exact representation involves a combinatorial explosion related to order-$k$ Voronoi diagrams, making it computationally prohibitive for large datasets. This paper introduces the witnessed k-distance, an approximation that maintains robustness while ensuring computational efficiency.

The Witnessed k-Distance Approach

The core innovation is the "witness" heuristic. Instead of considering the full arrangement of barycenters required by the exact DTM, the authors propose a linear-sized representation:

  1. Witnessed Barycenters: For each point $x$ in the input sample $P$, the algorithm identifies its $k-1$ nearest neighbors and computes their average position (barycenter).
  2. Linear Representation: By storing exactly one barycenter per input point, the representation size remains $O(N)$, where $N$ is the number of points.
  3. Power Distance: The witnessed k-distance ($d^w_{P,k}$) is defined as the power distance to this set of witnessed barycenters.

This approach restricts the search space to barycenters "witnessed" by actual data points, significantly reducing complexity without sacrificing the essential geometric properties of the DTM.

Theoretical Guarantees

The paper provides rigorous proofs for the stability and accuracy of the witnessed k-distance:

  • Multiplicative Bound: The authors establish that $d_{P,k} \leq d^w_{P,k} \leq (2 + \sqrt{2}) d_{P,k}$. This ensures the approximation stays within a constant factor of the exact DTM.
  • Stability: The approximation inherits the stability of the DTM with respect to the Wasserstein distance. If a noisy point cloud is close to the true shape in an optimal transport sense, the witnessed k-distance reliably recovers the underlying geometry.
  • Topological Inference: The method allows for the use of persistent homology to correctly identify Betti numbers (e.g., counting holes), even in the presence of significant noise.

Empirical Results

The effectiveness of the witnessed k-distance is demonstrated using synthetic models, such as a figure-eight convolved with Gaussian noise and additional outliers.

Figure 1: (a) Noisy data sampled from a figure-eight. (b) Sublevel sets of the witnessed k-distance successfully recovering the two-loop topology.

As shown in Figure 1, while standard distance functions might fail due to noise, the witnessed k-distance provides a clear recovery of the underlying topological structure. Computationally, the method scales linearly, requiring only a standard $k$-nearest neighbor search for each point.

Conclusion

The witnessed k-distance bridges the gap between the theoretical robustness of distance-to-measure functions and the practical requirements of large-scale data analysis. By providing a linear-sized approximation with strong topological guarantees, it enables robust geometric inference in the presence of outliers, a critical requirement for real-world topological data analysis.

Summary updated

Abstract

Distance function to a compact set plays a central role in several areas of computational geometry. Methods that rely on it are robust to the perturbations of the data by the Hausdorff noise, but fail in the presence of outliers. The recently introduced distance to a measure offers a solution by extending the distance function framework to reasoning about the geometry of probability measures, while maintaining theoretical guarantees about the quality of the inferred information. A combinatorial explosion hinders working with distance to a measure as an ordinary (power) distance function. In this paper, we analyze an approximation scheme that keeps the representation linear in the size of the input, while maintaining the guarantees on the inference quality close to those for the exact (but costly) representation.
BibTeX
@inproceedings{guibas2011witnessed,
  author = {Leonidas J. Guibas and Quentin Mérigot and Dmitriy Morozov},
  title = {{Witnessed k-Distance}},
  booktitle = {SCG},
  year = {2011},
  doi = {10.1145/1998196.1998205},
}
Figure