Sheaf-Theoretic Stratification Learning

Authors Adam Brown, Bei Wang



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.14.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Adam Brown
Bei Wang

Cite AsGet BibTex

Adam Brown and Bei Wang. Sheaf-Theoretic Stratification Learning. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.14

Abstract

In this paper, we investigate a sheaf-theoretic interpretation of stratification learning. Motivated by the work of Alexandroff (1937) and McCord (1978), we aim to redirect efforts in the computational topology of triangulated compact polyhedra to the much more computable realm of sheaves on partially ordered sets. Our main result is the construction of stratification learning algorithms framed in terms of a sheaf on a partially ordered set with the Alexandroff topology. We prove that the resulting decomposition is the unique minimal stratification for which the strata are homogeneous and the given sheaf is constructible. In particular, when we choose to work with the local homology sheaf, our algorithm gives an alternative to the local homology transfer algorithm given in Bendich et al. (2012), and the cohomology stratification algorithm given in Nanda (2017). We envision that our sheaf-theoretic algorithm could give rise to a larger class of stratification beyond homology-based stratification. This approach also points toward future applications of sheaf theory in the study of topological data analysis by illustrating the utility of the language of sheaf theory in generalizing existing algorithms.
Keywords
  • Sheaf theory
  • stratification learning
  • topological data analysis
  • stratification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Pavel Sergeyevich Alexandroff. Diskrete Räume. Mathematiceskii Sbornik, 2:501-518, 1937. Google Scholar
  2. Paul Bendich. Analyzing Stratified Spaces Using Persistent Versions of Intersection and Local Homology. PhD thesis, Duke University, 2008. Google Scholar
  3. Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov. Inferring local homology from sampled stratified spaces. IEEE Symposium on Foundations of Computer Science, pages 536-546, 2007. Google Scholar
  4. Paul Bendich and John Harer. Persistent intersection homology. Foundations of Computational Mathematics, 11:305-336, 2011. Google Scholar
  5. Paul Bendich, Bei Wang, and Sayan Mukherjee. Local homology transfer and stratification learning. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1355-1370, 2012. Google Scholar
  6. Adam Brown and Bei Wang. Sheaf-theoretic stratification learning. arXiv:1712.07734, 2017. Google Scholar
  7. Nicolás Cianci and Miguel Ottina. A new spectral sequence for homology of posets. Topology and its Applications, 217:1-19, 2017. Google Scholar
  8. Justin Curry. Sheaves, Cosheaves and Applications. PhD thesis, University of Pennsylvania, 2014. Google Scholar
  9. Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. American Mathematical Society, 2010. Google Scholar
  10. Mark Goresky and Robert MacPherson. Intersection homology I. Topology, 19:135-162, 1982. Google Scholar
  11. Mark Goresky and Robert MacPherson. Intersection homology II. Inventiones Mathematicae, 71:77-129, 1983. Google Scholar
  12. Mark Goresky and Robert MacPherson. Stratified Morse Theory. Springer-Verlag, 1988. Google Scholar
  13. Gloria Haro, Gregory Randall, and Guillermo Sapiro. Stratification learning: Detecting mixed density and dimensionality in high dimensional point clouds. Advances in Neural Information Processing Systems (NIPS), 17, 2005. Google Scholar
  14. Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002. Google Scholar
  15. Frances Clare Kirwan. An introduction to intersection homology theory. Chapman &Hall/CRC, 2006. Google Scholar
  16. Gilad Lerman and Teng Zhang. Probabilistic recovery of multiple subspaces in point clouds by geometric lp minimization. Annals of Statistics, 39(5):2686-2715, 2010. Google Scholar
  17. Michael C. McCord. Singular homology groups and homotopy groups of finite topological spaces. Duke Mathematical Journal, 33:465-474, 1978. Google Scholar
  18. Washington Mio. Homology manifolds. Annals of Mathematics Studies (AM-145), 1:323-343, 2000. Google Scholar
  19. James R. Munkres. Elements of algebraic topology. Addison-Wesley, Redwood City, CA, USA, 1984. Google Scholar
  20. Vidit Nanda. Local cohomology and stratification. ArXiv:1707.00354, 2017. Google Scholar
  21. Colin Rourke and Brian Sanderson. Homology stratifications and intersection homology. Geometry and Topology Monographs, 2:455-472, 1999. Google Scholar
  22. Allen Dudley Shepard. A Cellular Description Of The Derived Category Of A Stratified Space. PhD thesis, Brown University, 1985. Google Scholar
  23. Primoz Skraba and Bei Wang. Approximating local homology from samples. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 174-192, 2014. Google Scholar
  24. René Vidal, Yi Ma, and Shankar Sastry. Generalized principal component analysis (GPCA). IEEE Transactions on Pattern Analysis and Machine Intelligence, 27:1945-1959, 2005. Google Scholar
  25. Shmuel Weinberger. The topological classification of stratified spaces. University of Chicago Press, Chicago, IL, 1994. Google Scholar
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