5 Search Results for "Buchet, Mickael"

Document
DOI: 10.4230/LIPIcs.ESA.2024.29
A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels

Authors: Jean-Daniel Boissonnat and Kunal Dutta

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Computing persistent homology of large datasets using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, unlike in the case of persistent homology computation using the Euclidean distance or the k-distance, using Gaussian kernels involves significantly higher overhead, as all distance computations are in terms of the Gaussian kernel distance which is computationally more expensive. Further, most algorithmic implementations (e.g. Gudhi, Ripser, etc.) are based on Euclidean distances, so the question of finding a Euclidean embedding - preferably low-dimensional - that preserves the persistent homology computed with Gaussian kernels, is quite important. We consider the Gaussian kernel power distance (GKPD) given by Phillips, Wang and Zheng. Given an n-point dataset and a relative error parameter {ε} ∈ (0,1], we show that the persistent homology of the {Čech } filtration of the dataset computed using the GKPD can be approximately preserved using O({ε}^{-2}log n) dimensions, under a high stable rank condition. Our results also extend to the Delaunay filtration and the (simpler) case of the weighted Rips filtrations constructed using the GKPD. Compared to the Euclidean embedding for the Gaussian kernel function in ∼ n dimensions, which uses the Cholesky decomposition of the matrix of the kernel function applied to all pairs of data points, our embedding may also be viewed as dimensionality reduction - reducing the dimensionality from n to ∼ log n dimensions. Our proof utilizes the embedding of Chen and Phillips [ALT 2017], based on the Random Fourier Functions of Rahimi and Recht [NeurIPS 2007], together with two novel ingredients. The first one is a new decomposition of the squared radii of {Čech } simplices computed using the GKPD, in terms of the pairwise GKPDs between the vertices, which we state and prove. The second is a new concentration inequality for sums of cosine functions of Gaussian random vectors, which we call Gaussian cosine chaoses. We believe these are of independent interest and will find other applications in future.
Cite as

Jean-Daniel Boissonnat and Kunal Dutta. A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boissonnat_et_al:LIPIcs.ESA.2024.29,
  author =	{Boissonnat, Jean-Daniel and Dutta, Kunal},
  title =	{{A Euclidean Embedding for Computing Persistent Homology with Gaussian Kernels}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.29},
  URN =		{urn:nbn:de:0030-drops-211009},
  doi =		{10.4230/LIPIcs.ESA.2024.29},
  annote =	{Keywords: Persistent homology, Gaussian kernels, Random Fourier Features, Euclidean embedding}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.20
Sparse Higher Order Čech Filtrations

Authors: Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
For a finite set of balls of radius r, the k-fold cover is the space covered by at least k balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the k-fold filtration of the centers. For k = 1, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger k, it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the k-fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case k = 1, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points.
Cite as

Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber. Sparse Higher Order Čech Filtrations. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2023.20,
  author =	{Buchet, Micka\"{e}l and B. Dornelas, Bianca and Kerber, Michael},
  title =	{{Sparse Higher Order \v{C}ech Filtrations}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{20:1--20:17},
  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/entities/document/10.4230/LIPIcs.SoCG.2023.20},
  URN =		{urn:nbn:de:0030-drops-178709},
  doi =		{10.4230/LIPIcs.SoCG.2023.20},
  annote =	{Keywords: Sparsification, k-fold cover, Higher order \v{C}ech complexes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.15
Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension

Authors: Mickaël Buchet and Emerson G. Escolar

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
While persistent homology has taken strides towards becoming a widespread tool for data analysis, multidimensional persistence has proven more difficult to apply. One reason is the serious drawback of no longer having a concise and complete descriptor analogous to the persistence diagrams of the former. We propose a simple algebraic construction to illustrate the existence of infinite families of indecomposable persistence modules over regular grids of sufficient size. On top of providing a constructive proof of representation infinite type, we also provide realizations by topological spaces and Vietoris-Rips filtrations, showing that they can actually appear in real data and are not the product of degeneracies.
Cite as

Mickaël Buchet and Emerson G. Escolar. Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2018.15,
  author =	{Buchet, Micka\"{e}l and Escolar, Emerson G.},
  title =	{{Realizations of Indecomposable Persistence Modules of Arbitrarily Large Dimension}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.15},
  URN =		{urn:nbn:de:0030-drops-87287},
  doi =		{10.4230/LIPIcs.SoCG.2018.15},
  annote =	{Keywords: persistent homology, multi-persistence, representation theory, quivers, commutative ladders, Vietoris-Rips filtration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.23
Declutter and Resample: Towards Parameter Free Denoising

Authors: Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
In many data analysis applications the following scenario is commonplace: we are given a point set that is supposed to sample a hidden ground truth K in a metric space, but it got corrupted with noise so that some of the data points lie far away from K creating outliers also termed as ambient noise. One of the main goals of denoising algorithms is to eliminate such noise so that the curated data lie within a bounded Hausdorff distance of K. Popular denoising approaches such as deconvolution and thresholding often require the user to set several parameters and/or to choose an appropriate noise model while guaranteeing only asymptotic convergence. Our goal is to lighten this burden as much as possible while ensuring theoretical guarantees in all cases. Specifically, first, we propose a simple denoising algorithm that requires only a single parameter but provides a theoretical guarantee on the quality of the output on general input points. We argue that this single parameter cannot be avoided. We next present a simple algorithm that avoids even this parameter by paying for it with a slight strengthening of the sampling condition on the input points which is not unrealistic. We also provide some preliminary empirical evidence that our algorithms are effective in practice.
Cite as

Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Declutter and Resample: Towards Parameter Free Denoising. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2017.23,
  author =	{Buchet, Mickael and Dey, Tamal K. and Wang, Jiayuan and Wang, Yusu},
  title =	{{Declutter and Resample: Towards Parameter Free Denoising}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.23},
  URN =		{urn:nbn:de:0030-drops-72133},
  doi =		{10.4230/LIPIcs.SoCG.2017.23},
  annote =	{Keywords: denoising, parameter free, k-distance,compact sets}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.827
Topological Analysis of Scalar Fields with Outliers

Authors: Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Given a real-valued function f defined over a manifold M embedded in R^d, we are interested in recovering structural information about f from the sole information of its values on a finite sample P. Existing methods provide approximation to the persistence diagram of f when geometric noise and functional noise are bounded. However, they fail in the presence of aberrant values, also called outliers, both in theory and practice. We propose a new algorithm that deals with outliers. We handle aberrant functional values with a method inspired from the k-nearest neighbors regression and the local median filtering, while the geometric outliers are handled using the distance to a measure. Combined with topological results on nested filtrations, our algorithm performs robust topological analysis of scalar fields in a wider range of noise models than handled by current methods. We provide theoretical guarantees and experimental results on the quality of our approximation of the sampled scalar field.
Cite as

Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang. Topological Analysis of Scalar Fields with Outliers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 827-841, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SOCG.2015.827,
  author =	{Buchet, Micka\"{e}l and Chazal, Fr\'{e}d\'{e}ric and Dey, Tamal K. and Fan, Fengtao and Oudot, Steve Y. and Wang, Yusu},
  title =	{{Topological Analysis of Scalar Fields with Outliers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{827--841},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.827},
  URN =		{urn:nbn:de:0030-drops-51052},
  doi =		{10.4230/LIPIcs.SOCG.2015.827},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Scalar Field Analysis, Nested Rips Filtration, Distance to a Measure}
}
  • Refine by Author
  • 3 Buchet, Mickaël
  • 2 Dey, Tamal K.
  • 2 Wang, Yusu
  • 1 B. Dornelas, Bianca
  • 1 Boissonnat, Jean-Daniel
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Gaussian processes
  • 1 Theory of computation → Random projections and metric embeddings

  • Refine by Keyword
  • 1 Distance to a Measure
  • 1 Euclidean embedding
  • 1 Gaussian kernels
  • 1 Higher order Čech complexes
  • 1 Nested Rips Filtration
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2015
  • 1 2017
  • 1 2018
  • 1 2023
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact