Subsampling Methods for Persistent Homology

Frederic Chazal, Brittany Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, Larry Wasserman
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:2143-2151, 2015.

Abstract

Persistent homology is a multiscale method for analyzing the shape of sets and functions from point cloud data arising from an unknown distribution supported on those sets. When the size of the sample is large, direct computation of the persistent homology is prohibitive due to the combinatorial nature of the existing algorithms. We propose to compute the persistent homology of several subsamples of the data and then combine the resulting estimates. We study the risk of two estimators and we prove that the subsampling approach carries stable topological information while achieving a great reduction in computational complexity.

Cite this Paper


BibTeX
@InProceedings{pmlr-v37-chazal15, title = {Subsampling Methods for Persistent Homology}, author = {Chazal, Frederic and Fasy, Brittany and Lecci, Fabrizio and Michel, Bertrand and Rinaldo, Alessandro and Wasserman, Larry}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {2143--2151}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/chazal15.pdf}, url = {https://proceedings.mlr.press/v37/chazal15.html}, abstract = {Persistent homology is a multiscale method for analyzing the shape of sets and functions from point cloud data arising from an unknown distribution supported on those sets. When the size of the sample is large, direct computation of the persistent homology is prohibitive due to the combinatorial nature of the existing algorithms. We propose to compute the persistent homology of several subsamples of the data and then combine the resulting estimates. We study the risk of two estimators and we prove that the subsampling approach carries stable topological information while achieving a great reduction in computational complexity.} }
Endnote
%0 Conference Paper %T Subsampling Methods for Persistent Homology %A Frederic Chazal %A Brittany Fasy %A Fabrizio Lecci %A Bertrand Michel %A Alessandro Rinaldo %A Larry Wasserman %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-chazal15 %I PMLR %P 2143--2151 %U https://proceedings.mlr.press/v37/chazal15.html %V 37 %X Persistent homology is a multiscale method for analyzing the shape of sets and functions from point cloud data arising from an unknown distribution supported on those sets. When the size of the sample is large, direct computation of the persistent homology is prohibitive due to the combinatorial nature of the existing algorithms. We propose to compute the persistent homology of several subsamples of the data and then combine the resulting estimates. We study the risk of two estimators and we prove that the subsampling approach carries stable topological information while achieving a great reduction in computational complexity.
RIS
TY - CPAPER TI - Subsampling Methods for Persistent Homology AU - Frederic Chazal AU - Brittany Fasy AU - Fabrizio Lecci AU - Bertrand Michel AU - Alessandro Rinaldo AU - Larry Wasserman BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-chazal15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 2143 EP - 2151 L1 - http://proceedings.mlr.press/v37/chazal15.pdf UR - https://proceedings.mlr.press/v37/chazal15.html AB - Persistent homology is a multiscale method for analyzing the shape of sets and functions from point cloud data arising from an unknown distribution supported on those sets. When the size of the sample is large, direct computation of the persistent homology is prohibitive due to the combinatorial nature of the existing algorithms. We propose to compute the persistent homology of several subsamples of the data and then combine the resulting estimates. We study the risk of two estimators and we prove that the subsampling approach carries stable topological information while achieving a great reduction in computational complexity. ER -
APA
Chazal, F., Fasy, B., Lecci, F., Michel, B., Rinaldo, A. & Wasserman, L.. (2015). Subsampling Methods for Persistent Homology. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:2143-2151 Available from https://proceedings.mlr.press/v37/chazal15.html.

Related Material