Search Results

Documents authored by Sheth, Siddharth


Document
Sketching Persistence Diagrams

Authors: Donald R. Sheehy and Siddharth Sheth

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
Given a persistence diagram with n points, we give an algorithm that produces a sequence of n persistence diagrams converging in bottleneck distance to the input diagram, the ith of which has i distinct (weighted) points and is a 2-approximation to the closest persistence diagram with that many distinct points. For each approximation, we precompute the optimal matching between the ith and the (i+1)st. Perhaps surprisingly, the entire sequence of diagrams as well as the sequence of matchings can be represented in O(n) space. The main approach is to use a variation of the greedy permutation of the persistence diagram to give good Hausdorff approximations and assign weights to these subsets. We give a new algorithm to efficiently compute this permutation, despite the high implicit dimension of points in a persistence diagram due to the effect of the diagonal. The sketches are also structured to permit fast (linear time) approximations to the Hausdorff distance between diagrams - a lower bound on the bottleneck distance. For approximating the bottleneck distance, sketches can also be used to compute a linear-size neighborhood graph directly, obviating the need for geometric data structures used in state-of-the-art methods for bottleneck computation.

Cite as

Donald R. Sheehy and Siddharth Sheth. Sketching Persistence Diagrams. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{sheehy_et_al:LIPIcs.SoCG.2021.57,
  author =	{Sheehy, Donald R. and Sheth, Siddharth},
  title =	{{Sketching Persistence Diagrams}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.57},
  URN =		{urn:nbn:de:0030-drops-138569},
  doi =		{10.4230/LIPIcs.SoCG.2021.57},
  annote =	{Keywords: Bottleneck Distance, Persistent Homology, Approximate Persistence Diagrams}
}
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