LUMAWIG: Un-Bottling the Bottleneck Distance for Zero Dimensional Persistence Diagrams at Scale
Abstract
We present LUMÁWIG, a novel efficient algorithm to compute dimension zero bottleneck distance between two persistence diagrams of a specific kind which outperforms all other publicly available algorithm in runtime and accuracy. We bypass the overwhelming matching problem in previous implementations of the bottleneck distance, and prove that the zero dimensional bottleneck distance can be recovered from a very small number of matching cases. LUMÁWIG also generally enjoys linear complexity as shown by empirical tests. This allows us to scaleTDA to data sets of sizes encountered in machine learning and utilize persistence diagrams in a manner that goes beyond the simple use of the most persistent components.
Cite
Text
Ignacio et al. "LUMAWIG: Un-Bottling the Bottleneck Distance for Zero Dimensional Persistence Diagrams at Scale." NeurIPS 2020 Workshops: TDA_and_Beyond, 2020.Markdown
[Ignacio et al. "LUMAWIG: Un-Bottling the Bottleneck Distance for Zero Dimensional Persistence Diagrams at Scale." NeurIPS 2020 Workshops: TDA_and_Beyond, 2020.](https://mlanthology.org/neuripsw/2020/ignacio2020neuripsw-lumawig/)BibTeX
@inproceedings{ignacio2020neuripsw-lumawig,
title = {{LUMAWIG: Un-Bottling the Bottleneck Distance for Zero Dimensional Persistence Diagrams at Scale}},
author = {Ignacio, Paul Samuel and Bulauan, Jay-Anne and Uminsky, David},
booktitle = {NeurIPS 2020 Workshops: TDA_and_Beyond},
year = {2020},
url = {https://mlanthology.org/neuripsw/2020/ignacio2020neuripsw-lumawig/}
}