License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2023.38
URN: urn:nbn:de:0030-drops-178889
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17888/
Go to the corresponding LIPIcs Volume Portal

Roos Hoefgeest, Pepijn ; Slot, Lucas

The Christoffel-Darboux Kernel for Topological Data Analysis

pdf-format:
LIPIcs-SoCG-2023-38.pdf (3 MB)

Abstract

Persistent homology has been widely used to study the topology of point clouds in ℝⁿ. Standard approaches are very sensitive to outliers, and their computational complexity depends badly on the number of data points. In this paper we introduce a novel persistence module for a point cloud using the theory of Christoffel-Darboux kernels. This module is robust to (statistical) outliers in the data, and can be computed in time linear in the number of data points. We illustrate the benefits and limitations of our new module with various numerical examples in ℝⁿ, for n = 1, 2, 3. Our work expands upon recent applications of Christoffel-Darboux kernels in the context of statistical data analysis and geometric inference [Lasserre et al., 2022]. There, these kernels are used to construct a polynomial whose level sets capture the geometry of a point cloud in a precise sense. We show that the persistent homology associated to the sublevel set filtration of this polynomial is stable with respect to the Wasserstein distance. Moreover, we show that the persistent homology of this filtration can be computed in singly exponential time in the ambient dimension n, using a recent algorithm of Basu & Karisani [Basu and Karisani, 2022].

BibTeX - Entry

@InProceedings{rooshoefgeest_et_al:LIPIcs.SoCG.2023.38,
  author =	{Roos Hoefgeest, Pepijn and Slot, Lucas},
  title =	{{The Christoffel-Darboux Kernel for Topological Data Analysis}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17888},
  URN =		{urn:nbn:de:0030-drops-178889},
  doi =		{10.4230/LIPIcs.SoCG.2023.38},
  annote =	{Keywords: Topological Data Analysis, Geometric Inference, Christoffel-Darboux Kernels, Persistent Homology, Wasserstein Distance, Semi-Algebraic Sets}
}

Keywords: Topological Data Analysis, Geometric Inference, Christoffel-Darboux Kernels, Persistent Homology, Wasserstein Distance, Semi-Algebraic Sets
Collection: 39th International Symposium on Computational Geometry (SoCG 2023)
Issue Date: 2023
Date of publication: 09.06.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI